[lkml]   [2014]   [Jan]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: Memory allocator semantics
    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.


    > - 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.


    > - 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).


    > - 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 from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2014-01-03 09:41    [W:4.098 / U:0.000 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site