Re: Memory allocator semantics

Josh Triplett
2014-01-03T05:47:39Z

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*?".

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

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

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

- Josh Triplett