On Thu, Jan 02, 2014 at 09:47:00PM -0800, Josh Triplett wrote: > On Thu, Jan 02, 2014 at 09:14:17PM -0800, Paul E. McKenney wrote: > > On Thu, Jan 02, 2014 at 07:39:07PM -0800, Josh Triplett wrote: > > > On Thu, Jan 02, 2014 at 12:33:20PM -0800, Paul E. McKenney wrote: > > > > Hello! > > > > > > > > From what I can see, the Linux-kernel's SLAB, SLOB, and SLUB memory > > > > allocators would deal with the following sort of race: > > > > > > > > A. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(gp) = r1; > > > > > > > > CPU 1: r2 = ACCESS_ONCE(gp); if (r2) kfree(r2); > > > > > > > > However, my guess is that this should be considered an accident of the > > > > current implementation rather than a feature. The reason for this is > > > > that I cannot see how you would usefully do (A) above without also allowing > > > > (B) and (C) below, both of which look to me to be quite destructive: > > > > > > (A) only seems OK if "gp" is guaranteed to be NULL beforehand, *and* if > > > no other CPUs can possibly do what CPU 1 is doing in parallel. Even > > > then, it seems questionable how this could ever be used successfully in > > > practice. > > > > > > This seems similar to the TCP simultaneous-SYN case: theoretically > > > possible, absurd in practice. > > > > Heh! > > > > Agreed on the absurdity, but my quick look and slab/slob/slub leads > > me to believe that current Linux kernel would actually do something > > sensible in this case. But only because they don't touch the actual > > memory. DYNIX/ptx would have choked on it, IIRC. > > Based on this and the discussion at the bottom of your mail, I think I'm > starting to understand what you're getting at; this seems like less of a > question of "could this usefully happen?" and more "does the allocator > know how to protect *itself*?". Or perhaps "What are the rules when a concurrent program interacts with a memory allocator?" Like the set you provided below. ;-) > > > > But I thought I should ask the experts. > > > > > > > > So, am I correct that kernel hackers are required to avoid "drive-by" > > > > kfree()s of kmalloc()ed memory? > > > > > > Don't kfree things that are in use, and synchronize to make sure all > > > CPUs agree about "in use", yes. > > > > For example, ensure that each kmalloc() happens unambiguously before the > > corresponding kfree(). ;-) > > That too, yes. :) > > > > > PS. To the question "Why would anyone care about (A)?", then answer > > > > is "Inquiring programming-language memory-model designers want > > > > to know." > > > > > > I find myself wondering about the original form of the question, since > > > I'd hope that programming-languge memory-model designers would > > > understand the need for synchronization around reclaiming memory. > > > > I think that they do now. The original form of the question was as > > follows: > > > > But my intuition at the moment is that allowing racing > > accesses and providing pointer atomicity leads to a much more > > complicated and harder to explain model. You have to deal > > with initialization issues and OOTA problems without atomics. > > And the implementation has to deal with cross-thread visibility > > of malloc meta-information, which I suspect will be expensive. > > You now essentially have to be able to malloc() in one thread, > > transfer the pointer via a race to another thread, and free() > > in the second thread. That’s hard unless malloc() and free() > > always lock (as I presume they do in the Linux kernel). > > As mentioned above, this makes much more sense now. This seems like a > question of how the allocator protects its *own* internal data > structures, rather than whether the allocator can usefully be used for > the cases you mentioned above. And that's a reasonable question to ask > if you're building a language memory model for a language with malloc > and free as part of its standard library. > > To roughly sketch out some general rules that might work as a set of > scalable design constraints for malloc/free: > > - malloc may always return any unallocated memory; it has no obligation > to avoid returning memory that was just recently freed. In fact, an > implementation may even be particularly *likely* to return memory that > was just recently freed, for performance reasons. Any program which > assumes a delay or a memory barrier before memory reuse is broken. Agreed. > - Multiple calls to free on the same memory will produce undefined > behavior, and in particular may result in a well-known form of > security hole. free has no obligation to protect itself against > multiple calls to free on the same memory, unless otherwise specified > as part of some debugging mode. This holds whether the calls to free > occur in series or in parallel (e.g. two or more calls racing with > each other). It is the job of the calling program to avoid calling > free multiple times on the same memory, such as via reference > counting, RCU, or some other mechanism. Yep! > - It is the job of the calling program to avoid calling free on memory > that is currently in use, such as via reference counting, RCU, or some > other mechanism. Accessing memory after reclaiming it will produce > undefined behavior. This includes calling free on memory concurrently > with accesses to that memory (e.g. via a race). Yep! > - malloc and free must work correctly when concurrently called from > multiple threads without synchronization. Any synchronization or > memory barriers required internally by the implementations must be > provided by the implementation. However, an implementation is not > required to use any particular form of synchronization, such as > locking or memory barriers, and the caller of malloc or free may not > make any assumptions about the ordering of its own operations > surrounding those calls. For example, an implementation may use > per-CPU memory pools, and only use synchronization when it cannot > satisfy an allocation request from the current CPU's pool. Yep, though in C/C++11 this comes out something very roughly like: "A free() involving a given byte of memory synchronizes-with a later alloc() returning a block containing that block of memory." > - An implementation of free must support being called on any memory > allocated by the same implementation of malloc, at any time, from any > CPU. In particular, a call to free on memory freshly malloc'd on > another CPU, with no intervening synchronization between the two > calls, must succeed and reclaim the memory. However, the actual calls > to malloc and free must not race with each other; in particular, the > pointer value returned by malloc is not valid (for access or for calls > to free) until malloc itself has returned. (Such a race would require > the caller of free to divine the value returned by malloc before > malloc returns.) Thus, the implementations of malloc and free may > safely assume a data dependency (via the returned pointer value > itself) between the call to malloc and the call to free; such a > dependency may allow further assumptions about memory ordering based > on the platform's memory model. I would be OK requiring the user to have a happens-before relationship between an allocation and a subsequent matching free. > > But the first I heard of it was something like litmus test (A) above. > > > > (And yes, I already disabused them of their notion that Linux kernel > > kmalloc() and kfree() always lock.) > > That much does seem like an easy assumption to make if you've never > thought about how to write a scalable allocator. The concept of per-CPU > memory pools is the very first thing that should come to mind when > thinking the words "scalable" and "allocator" in the same sentence, but > first you have to get programming-language memory-model designers > thinking the word "scalable". ;) Well, given that it was not obvious to me the first year or so that I was doing parallel programming, I cannot give them too much trouble. Of course, that was some time ago. ;-) Thanx, Paul -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@xxxxxxxxx. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>