Re: Memory allocator semantics

Paul E. McKenney
2014-01-03T07:57:46Z

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