From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ob0-f170.google.com (mail-ob0-f170.google.com [209.85.214.170]) by kanga.kvack.org (Postfix) with ESMTP id D578E6B0031 for ; Thu, 2 Jan 2014 15:33:40 -0500 (EST) Received: by mail-ob0-f170.google.com with SMTP id wp18so15015846obc.29 for ; Thu, 02 Jan 2014 12:33:40 -0800 (PST) Received: from e39.co.us.ibm.com (e39.co.us.ibm.com. [32.97.110.160]) by mx.google.com with ESMTPS id jb8si45338889obb.105.2014.01.02.12.33.39 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Thu, 02 Jan 2014 12:33:39 -0800 (PST) Received: from /spool/local by e39.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 2 Jan 2014 13:33:39 -0700 Received: from b03cxnp07028.gho.boulder.ibm.com (b03cxnp07028.gho.boulder.ibm.com [9.17.130.15]) by d03dlp03.boulder.ibm.com (Postfix) with ESMTP id 68ABA19D803E for ; Thu, 2 Jan 2014 13:33:27 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp07028.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id s02KXQae63766550 for ; Thu, 2 Jan 2014 21:33:26 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id s02Kakwx008935 for ; Thu, 2 Jan 2014 13:36:46 -0700 Date: Thu, 2 Jan 2014 12:33:20 -0800 From: "Paul E. McKenney" Subject: Memory allocator semantics Message-ID: <20140102203320.GA27615@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Sender: owner-linux-mm@kvack.org List-ID: To: linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com 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: B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); This results in the memory being on two different freelists. C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; This results in the memory being used by two different CPUs, each of which believe that they have sole access. 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? Thanx, Paul PS. To the question "Why would anyone care about (A)?", then answer is "Inquiring programming-language memory-model designers want to know." -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wi0-f180.google.com (mail-wi0-f180.google.com [209.85.212.180]) by kanga.kvack.org (Postfix) with ESMTP id 67DCC6B0035 for ; Thu, 2 Jan 2014 22:39:16 -0500 (EST) Received: by mail-wi0-f180.google.com with SMTP id hm19so58094wib.7 for ; Thu, 02 Jan 2014 19:39:15 -0800 (PST) Received: from relay3-d.mail.gandi.net (relay3-d.mail.gandi.net. [2001:4b98:c:538::195]) by mx.google.com with ESMTPS id k1si22392298wjz.126.2014.01.02.19.39.15 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Thu, 02 Jan 2014 19:39:15 -0800 (PST) Date: Thu, 2 Jan 2014 19:39:07 -0800 From: Josh Triplett Subject: Re: Memory allocator semantics Message-ID: <20140103033906.GB2983@leaf> References: <20140102203320.GA27615@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20140102203320.GA27615@linux.vnet.ibm.com> Sender: owner-linux-mm@kvack.org List-ID: To: "Paul E. McKenney" Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com 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. > B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > This results in the memory being on two different freelists. That's a straightforward double-free bug. You need some kind of synchronization there to ensure that only one call to kfree occurs. > C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; > > This results in the memory being used by two different CPUs, > each of which believe that they have sole access. This is not OK either: CPU 2 has called kfree on a pointer that CPU 1 still considers alive, and again, the CPUs haven't used any form of synchronization to prevent that. > 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. > 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. - Josh Triplett -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ob0-f174.google.com (mail-ob0-f174.google.com [209.85.214.174]) by kanga.kvack.org (Postfix) with ESMTP id 2569F6B0035 for ; Fri, 3 Jan 2014 00:14:40 -0500 (EST) Received: by mail-ob0-f174.google.com with SMTP id wn1so15170368obc.19 for ; Thu, 02 Jan 2014 21:14:39 -0800 (PST) Received: from e32.co.us.ibm.com (e32.co.us.ibm.com. [32.97.110.150]) by mx.google.com with ESMTPS id p8si46207501oeq.43.2014.01.02.21.14.38 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Thu, 02 Jan 2014 21:14:38 -0800 (PST) Received: from /spool/local by e32.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 2 Jan 2014 22:14:37 -0700 Received: from b03cxnp08027.gho.boulder.ibm.com (b03cxnp08027.gho.boulder.ibm.com [9.17.130.19]) by d03dlp01.boulder.ibm.com (Postfix) with ESMTP id D28B01FF001A for ; Thu, 2 Jan 2014 22:14:07 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp08027.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id s035ESYF8585602 for ; Fri, 3 Jan 2014 06:14:28 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id s035HkHk024978 for ; Thu, 2 Jan 2014 22:17:46 -0700 Date: Thu, 2 Jan 2014 21:14:17 -0800 From: "Paul E. McKenney" Subject: Re: Memory allocator semantics Message-ID: <20140103051417.GT19211@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <20140103033906.GB2983@leaf> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20140103033906.GB2983@leaf> Sender: owner-linux-mm@kvack.org List-ID: To: Josh Triplett Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com 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. And the fact that slab/slob/slub seem to handle (A) seemed bizarre enough to be worth asking the question. > > B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > > > CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); > > > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > > > This results in the memory being on two different freelists. > > That's a straightforward double-free bug. You need some kind of > synchronization there to ensure that only one call to kfree occurs. Yep! > > C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > > > CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; > > > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > > > CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; > > > > This results in the memory being used by two different CPUs, > > each of which believe that they have sole access. > > This is not OK either: CPU 2 has called kfree on a pointer that CPU 1 > still considers alive, and again, the CPUs haven't used any form of > synchronization to prevent that. Agreed. > > 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(). ;-) > > 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. Thata??s hard unless malloc() and free() always lock (as I presume they do in the Linux kernel). 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.) Thanx, Paul -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wi0-f182.google.com (mail-wi0-f182.google.com [209.85.212.182]) by kanga.kvack.org (Postfix) with ESMTP id C5CF96B0035 for ; Fri, 3 Jan 2014 00:47:12 -0500 (EST) Received: by mail-wi0-f182.google.com with SMTP id en1so115427wid.3 for ; Thu, 02 Jan 2014 21:47:12 -0800 (PST) Received: from relay3-d.mail.gandi.net (relay3-d.mail.gandi.net. [2001:4b98:c:538::195]) by mx.google.com with ESMTPS id dt8si269378wib.9.2014.01.02.21.47.11 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Thu, 02 Jan 2014 21:47:11 -0800 (PST) Date: Thu, 2 Jan 2014 21:47:00 -0800 From: Josh Triplett Subject: Re: Memory allocator semantics Message-ID: <20140103054700.GA4865@leaf> References: <20140102203320.GA27615@linux.vnet.ibm.com> <20140103033906.GB2983@leaf> <20140103051417.GT19211@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20140103051417.GT19211@linux.vnet.ibm.com> Content-Transfer-Encoding: quoted-printable Sender: owner-linux-mm@kvack.org List-ID: To: "Paul E. McKenney" Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com 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! > > >=20 > > > From what I can see, the Linux-kernel's SLAB, SLOB, and SLUB memory > > > allocators would deal with the following sort of race: > > >=20 > > > A. CPU 0: r1 =3D kmalloc(...); ACCESS_ONCE(gp) =3D r1; > > >=20 > > > CPU 1: r2 =3D ACCESS_ONCE(gp); if (r2) kfree(r2); > > >=20 > > > 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= : > >=20 > > (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. > >=20 > > This seems similar to the TCP simultaneous-SYN case: theoretically > > possible, absurd in practice. >=20 > Heh! >=20 > 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. > > >=20 > > > So, am I correct that kernel hackers are required to avoid "drive-b= y" > > > kfree()s of kmalloc()ed memory? > >=20 > > Don't kfree things that are in use, and synchronize to make sure all > > CPUs agree about "in use", yes. >=20 > For example, ensure that each kmalloc() happens unambiguously before th= e > corresponding kfree(). ;-) That too, yes. :) > > > PS. To the question "Why would anyone care about (A)?", then answe= r > > > is "Inquiring programming-language memory-model designers want > > > to know." > >=20 > > I find myself wondering about the original form of the question, sinc= e > > I'd hope that programming-languge memory-model designers would > > understand the need for synchronization around reclaiming memory. >=20 > I think that they do now. The original form of the question was as > follows: >=20 > 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=E2=80=99s 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. >=20 > (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 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qc0-f179.google.com (mail-qc0-f179.google.com [209.85.216.179]) by kanga.kvack.org (Postfix) with ESMTP id D29EE6B0035 for ; Fri, 3 Jan 2014 02:57:46 -0500 (EST) Received: by mail-qc0-f179.google.com with SMTP id i8so14803734qcq.10 for ; Thu, 02 Jan 2014 23:57:45 -0800 (PST) Received: from e36.co.us.ibm.com (e36.co.us.ibm.com. [32.97.110.154]) by mx.google.com with ESMTPS id l3si57933257qac.14.2014.01.02.23.57.44 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Thu, 02 Jan 2014 23:57:44 -0800 (PST) Received: from /spool/local by e36.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Fri, 3 Jan 2014 00:57:43 -0700 Received: from b03cxnp08026.gho.boulder.ibm.com (b03cxnp08026.gho.boulder.ibm.com [9.17.130.18]) by d03dlp01.boulder.ibm.com (Postfix) with ESMTP id 8D3721FF001E for ; Fri, 3 Jan 2014 00:57:14 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp08026.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id s037vZn12294204 for ; Fri, 3 Jan 2014 08:57:35 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id s0380rfo016229 for ; Fri, 3 Jan 2014 01:00:53 -0700 Date: Thu, 2 Jan 2014 23:57:27 -0800 From: "Paul E. McKenney" Subject: Re: Memory allocator semantics Message-ID: <20140103075727.GU19211@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <20140103033906.GB2983@leaf> <20140103051417.GT19211@linux.vnet.ibm.com> <20140103054700.GA4865@leaf> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20140103054700.GA4865@leaf> Sender: owner-linux-mm@kvack.org List-ID: To: Josh Triplett Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com 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. Thata??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@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wi0-f179.google.com (mail-wi0-f179.google.com [209.85.212.179]) by kanga.kvack.org (Postfix) with ESMTP id 26A6C6B0035 for ; Fri, 3 Jan 2014 03:42:45 -0500 (EST) Received: by mail-wi0-f179.google.com with SMTP id z2so215330wiv.0 for ; Fri, 03 Jan 2014 00:42:44 -0800 (PST) Received: from relay3-d.mail.gandi.net (relay3-d.mail.gandi.net. [2001:4b98:c:538::195]) by mx.google.com with ESMTPS id tn8si22711151wjc.83.2014.01.03.00.42.43 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Fri, 03 Jan 2014 00:42:44 -0800 (PST) Date: Fri, 3 Jan 2014 00:42:36 -0800 From: Josh Triplett Subject: Re: Memory allocator semantics Message-ID: <20140103084236.GA5992@leaf> References: <20140102203320.GA27615@linux.vnet.ibm.com> <20140103033906.GB2983@leaf> <20140103051417.GT19211@linux.vnet.ibm.com> <20140103054700.GA4865@leaf> <20140103075727.GU19211@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20140103075727.GU19211@linux.vnet.ibm.com> Content-Transfer-Encoding: quoted-printable Sender: owner-linux-mm@kvack.org List-ID: To: "Paul E. McKenney" Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com On Thu, Jan 02, 2014 at 11:57:27PM -0800, Paul E. McKenney wrote: > 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! > > > > >=20 > > > > > From what I can see, the Linux-kernel's SLAB, SLOB, and SLUB me= mory > > > > > allocators would deal with the following sort of race: > > > > >=20 > > > > > A. CPU 0: r1 =3D kmalloc(...); ACCESS_ONCE(gp) =3D r1; > > > > >=20 > > > > > CPU 1: r2 =3D ACCESS_ONCE(gp); if (r2) kfree(r2); > > > > >=20 > > > > > However, my guess is that this should be considered an accident= of the > > > > > current implementation rather than a feature. The reason for t= his is > > > > > that I cannot see how you would usefully do (A) above without a= lso allowing > > > > > (B) and (C) below, both of which look to me to be quite destruc= tive: > > > >=20 > > > > (A) only seems OK if "gp" is guaranteed to be NULL beforehand, *a= nd* if > > > > no other CPUs can possibly do what CPU 1 is doing in parallel. E= ven > > > > then, it seems questionable how this could ever be used successfu= lly in > > > > practice. > > > >=20 > > > > This seems similar to the TCP simultaneous-SYN case: theoreticall= y > > > > possible, absurd in practice. > > >=20 > > > Heh! > > >=20 > > > 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 actua= l > > > memory. DYNIX/ptx would have choked on it, IIRC. > >=20 > > 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 o= f a > > question of "could this usefully happen?" and more "does the allocato= r > > know how to protect *itself*?". >=20 > 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. > > > > >=20 > > > > > So, am I correct that kernel hackers are required to avoid "dri= ve-by" > > > > > kfree()s of kmalloc()ed memory? > > > >=20 > > > > Don't kfree things that are in use, and synchronize to make sure = all > > > > CPUs agree about "in use", yes. > > >=20 > > > For example, ensure that each kmalloc() happens unambiguously befor= e the > > > corresponding kfree(). ;-) > >=20 > > That too, yes. :) > >=20 > > > > > PS. To the question "Why would anyone care about (A)?", then a= nswer > > > > > is "Inquiring programming-language memory-model designers = want > > > > > to know." > > > >=20 > > > > 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. > > >=20 > > > I think that they do now. The original form of the question was as > > > follows: > > >=20 > > > 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=E2=80=99s hard unless malloc() and fre= e() > > > always lock (as I presume they do in the Linux kernel). > >=20 > > 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 fo= r > > the cases you mentioned above. And that's a reasonable question to a= sk > > if you're building a language memory model for a language with malloc > > and free as part of its standard library. > >=20 > > To roughly sketch out some general rules that might work as a set of > > scalable design constraints for malloc/free: > >=20 > > - malloc may always return any unallocated memory; it has no obligati= on > > to avoid returning memory that was just recently freed. In fact, a= n > > implementation may even be particularly *likely* to return memory t= hat > > was just recently freed, for performance reasons. Any program whic= h > > assumes a delay or a memory barrier before memory reuse is broken. >=20 > Agreed. >=20 > > - 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 specifi= ed > > as part of some debugging mode. This holds whether the calls to fr= ee > > 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. >=20 > Yep! >=20 > > - It is the job of the calling program to avoid calling free on memor= y > > that is currently in use, such as via reference counting, RCU, or s= ome > > other mechanism. Accessing memory after reclaiming it will produce > > undefined behavior. This includes calling free on memory concurren= tly > > with accesses to that memory (e.g. via a race). >=20 > Yep! >=20 > > - 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 no= t > > 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. >=20 > 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." Gah. That doesn't seem like a memory-ordering guarantee the allocator should have to provide for its caller, and I can easily think of allocator structures that wouldn't guarantee it without the inclusion of an explicit memory barrier. (Also, I assume the last use of "block" in that sentence should have been "byte"?) > > - An implementation of free must support being called on any memory > > allocated by the same implementation of malloc, at any time, from a= ny > > 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 ca= lls > > to malloc and free must not race with each other; in particular, th= e > > pointer value returned by malloc is not valid (for access or for ca= lls > > to free) until malloc itself has returned. (Such a race would requ= ire > > 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 base= d > > on the platform's memory model. >=20 > I would be OK requiring the user to have a happens-before relationship > between an allocation and a subsequent matching free. I *think* that's the right formal relationship I'm suggesting, yes. Mostly I'm suggesting that since the only sensible way for the pointer value you're passing to free to have come into existence is to have received it from malloc at some point in the past (as opposed to magically divining its value), it's not so much "requiring the user to have a happens-before relationship" as "not allowing the user to randomly make up pointers and free them, even if they happen to match the value being returned from a concurrent malloc". Because that's the only way I can think of for malloc and free to race on the same pointer. In any case, let me know if the rules sketched above end up proving useful as part of the requirements for malloc/free. - Josh Triplett -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ob0-f169.google.com (mail-ob0-f169.google.com [209.85.214.169]) by kanga.kvack.org (Postfix) with ESMTP id 38BF96B0031 for ; Sat, 8 Feb 2014 21:00:13 -0500 (EST) Received: by mail-ob0-f169.google.com with SMTP id wo20so5836516obc.28 for ; Sat, 08 Feb 2014 18:00:12 -0800 (PST) Received: from e31.co.us.ibm.com (e31.co.us.ibm.com. [32.97.110.149]) by mx.google.com with ESMTPS id rk9si5282629obb.51.2014.02.08.18.00.11 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Sat, 08 Feb 2014 18:00:12 -0800 (PST) Received: from /spool/local by e31.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Sat, 8 Feb 2014 19:00:11 -0700 Received: from b03cxnp08025.gho.boulder.ibm.com (b03cxnp08025.gho.boulder.ibm.com [9.17.130.17]) by d03dlp01.boulder.ibm.com (Postfix) with ESMTP id 91DC11FF001B for ; Sat, 8 Feb 2014 19:00:08 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp08025.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id s192089u31260778 for ; Sun, 9 Feb 2014 03:00:08 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id s1923S1i009209 for ; Sat, 8 Feb 2014 19:03:29 -0700 Date: Sat, 8 Feb 2014 18:00:04 -0800 From: "Paul E. McKenney" Subject: Re: Memory allocator semantics Message-ID: <20140209020004.GY4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <52F60699.8010204@iki.fi> Sender: owner-linux-mm@kvack.org List-ID: To: Pekka Enberg Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com On Sat, Feb 08, 2014 at 12:27:37PM +0200, Pekka Enberg wrote: > Hi Paul, > > On 01/02/2014 10:33 PM, Paul E. McKenney wrote: > > 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: > > > >B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > > > CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); > > > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > > > This results in the memory being on two different freelists. > > > >C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > > > CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; > > > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > > > CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; > > > > This results in the memory being used by two different CPUs, > > each of which believe that they have sole access. > > > >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? > > So to be completely honest, I don't understand what is the race in > (A) that concerns the *memory allocator*. I also don't what the > memory allocator can do in (B) and (C) which look like double-free > and use-after-free, respectively, to me. :-) >>From what I can see, (A) works by accident, but is kind of useless because you allocate and free the memory without touching it. (B) and (C) are the lightest touches I could imagine, and as you say, both are bad. So I believe that it is reasonable to prohibit (A). Or is there some use for (A) that I am missing? Thanx, Paul -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pb0-f78.google.com (mail-pb0-f78.google.com [209.85.160.78]) by kanga.kvack.org (Postfix) with ESMTP id 7FD136B0031 for ; Sun, 9 Feb 2014 09:14:28 -0500 (EST) Received: by mail-pb0-f78.google.com with SMTP id jt11so25859pbb.1 for ; Sun, 09 Feb 2014 06:14:27 -0800 (PST) Received: from out4-smtp.messagingengine.com (out4-smtp.messagingengine.com. [66.111.4.28]) by mx.google.com with ESMTPS id va10si8168057pbc.308.2014.02.08.02.27.39 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 08 Feb 2014 02:27:40 -0800 (PST) Received: from compute4.internal (compute4.nyi.mail.srv.osa [10.202.2.44]) by gateway1.nyi.mail.srv.osa (Postfix) with ESMTP id 110A520C7F for ; Sat, 8 Feb 2014 05:27:39 -0500 (EST) Message-ID: <52F60699.8010204@iki.fi> Date: Sat, 08 Feb 2014 12:27:37 +0200 From: Pekka Enberg MIME-Version: 1.0 Subject: Re: Memory allocator semantics References: <20140102203320.GA27615@linux.vnet.ibm.com> In-Reply-To: <20140102203320.GA27615@linux.vnet.ibm.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: paulmck@linux.vnet.ibm.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Hi Paul, On 01/02/2014 10:33 PM, Paul E. McKenney wrote: > 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: > > B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > This results in the memory being on two different freelists. > > C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; > > This results in the memory being used by two different CPUs, > each of which believe that they have sole access. > > 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? So to be completely honest, I don't understand what is the race in (A) that concerns the *memory allocator*. I also don't what the memory allocator can do in (B) and (C) which look like double-free and use-after-free, respectively, to me. :-) Pekka -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qc0-f169.google.com (mail-qc0-f169.google.com [209.85.216.169]) by kanga.kvack.org (Postfix) with ESMTP id 2B1406B0037 for ; Mon, 10 Feb 2014 14:08:02 -0500 (EST) Received: by mail-qc0-f169.google.com with SMTP id w7so11434524qcr.0 for ; Mon, 10 Feb 2014 11:08:01 -0800 (PST) Received: from qmta13.emeryville.ca.mail.comcast.net (qmta13.emeryville.ca.mail.comcast.net. [2001:558:fe2d:44:76:96:27:243]) by mx.google.com with ESMTP id w9si10676896qgw.173.2014.02.10.11.08.00 for ; Mon, 10 Feb 2014 11:08:01 -0800 (PST) Date: Mon, 10 Feb 2014 13:07:58 -0600 (CST) From: Christoph Lameter Subject: Re: Memory allocator semantics In-Reply-To: <52F60699.8010204@iki.fi> Message-ID: References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-linux-mm@kvack.org List-ID: To: Pekka Enberg Cc: paulmck@linux.vnet.ibm.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, penberg@kernel.org, mpm@selenic.com On Sat, 8 Feb 2014, Pekka Enberg wrote: > So to be completely honest, I don't understand what is the race in (A) that > concerns the *memory allocator*. I also don't what the memory allocator can > do in (B) and (C) which look like double-free and use-after-free, > respectively, to me. :-) Well it seems to be some academic mind game to me. Does an invocation of the allocator have barrier semantics or not? -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pa0-f53.google.com (mail-pa0-f53.google.com [209.85.220.53]) by kanga.kvack.org (Postfix) with ESMTP id 758F26B0031 for ; Tue, 11 Feb 2014 03:50:26 -0500 (EST) Received: by mail-pa0-f53.google.com with SMTP id lj1so7326967pab.26 for ; Tue, 11 Feb 2014 00:50:26 -0800 (PST) Received: from mail-pa0-x229.google.com (mail-pa0-x229.google.com [2607:f8b0:400e:c03::229]) by mx.google.com with ESMTPS id qx4si18242970pbc.75.2014.02.11.00.50.25 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 11 Feb 2014 00:50:25 -0800 (PST) Received: by mail-pa0-f41.google.com with SMTP id fa1so7409744pad.0 for ; Tue, 11 Feb 2014 00:50:25 -0800 (PST) MIME-Version: 1.0 In-Reply-To: <20140209020004.GY4250@linux.vnet.ibm.com> References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140209020004.GY4250@linux.vnet.ibm.com> Date: Tue, 11 Feb 2014 10:50:24 +0200 Message-ID: Subject: Re: Memory allocator semantics From: Pekka Enberg Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Paul McKenney Cc: "linux-mm@kvack.org" , LKML , Christoph Lameter , Matt Mackall Hi Paul, On Sun, Feb 9, 2014 at 4:00 AM, Paul E. McKenney wrote: > From what I can see, (A) works by accident, but is kind of useless because > you allocate and free the memory without touching it. (B) and (C) are the > lightest touches I could imagine, and as you say, both are bad. So I > believe that it is reasonable to prohibit (A). > > Or is there some use for (A) that I am missing? So again, there's nothing in (A) that the memory allocator is concerned about. kmalloc() makes no guarantees whatsoever about the visibility of "r1" across CPUs. If you're saying that there's an implicit barrier between kmalloc() and kfree(), that's an unintended side-effect, not a design decision AFAICT. Pekka -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oa0-f46.google.com (mail-oa0-f46.google.com [209.85.219.46]) by kanga.kvack.org (Postfix) with ESMTP id B2ECA6B0031 for ; Tue, 11 Feb 2014 07:09:22 -0500 (EST) Received: by mail-oa0-f46.google.com with SMTP id n16so8971376oag.5 for ; Tue, 11 Feb 2014 04:09:22 -0800 (PST) Received: from e34.co.us.ibm.com (e34.co.us.ibm.com. [32.97.110.152]) by mx.google.com with ESMTPS id ns8si9401660obc.22.2014.02.11.04.09.21 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Tue, 11 Feb 2014 04:09:21 -0800 (PST) Received: from /spool/local by e34.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 11 Feb 2014 05:09:21 -0700 Received: from b03cxnp08025.gho.boulder.ibm.com (b03cxnp08025.gho.boulder.ibm.com [9.17.130.17]) by d03dlp03.boulder.ibm.com (Postfix) with ESMTP id D2D6919D8036 for ; Tue, 11 Feb 2014 05:09:17 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp08025.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id s1BC9Icm10420730 for ; Tue, 11 Feb 2014 13:09:18 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id s1BCCdm0005162 for ; Tue, 11 Feb 2014 05:12:39 -0700 Date: Tue, 11 Feb 2014 04:09:16 -0800 From: "Paul E. McKenney" Subject: Re: Memory allocator semantics Message-ID: <20140211120915.GP4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140209020004.GY4250@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: owner-linux-mm@kvack.org List-ID: To: Pekka Enberg Cc: "linux-mm@kvack.org" , LKML , Christoph Lameter , Matt Mackall On Tue, Feb 11, 2014 at 10:50:24AM +0200, Pekka Enberg wrote: > Hi Paul, > > On Sun, Feb 9, 2014 at 4:00 AM, Paul E. McKenney > wrote: > > From what I can see, (A) works by accident, but is kind of useless because > > you allocate and free the memory without touching it. (B) and (C) are the > > lightest touches I could imagine, and as you say, both are bad. So I > > believe that it is reasonable to prohibit (A). > > > > Or is there some use for (A) that I am missing? > > So again, there's nothing in (A) that the memory allocator is > concerned about. kmalloc() makes no guarantees whatsoever about the > visibility of "r1" across CPUs. If you're saying that there's an > implicit barrier between kmalloc() and kfree(), that's an unintended > side-effect, not a design decision AFAICT. Thank you. That was what I suspected, and I believe that it is a completely reasonable response to (A). Thanx, Paul -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oa0-f52.google.com (mail-oa0-f52.google.com [209.85.219.52]) by kanga.kvack.org (Postfix) with ESMTP id 47EFD6B0031 for ; Tue, 11 Feb 2014 07:14:32 -0500 (EST) Received: by mail-oa0-f52.google.com with SMTP id i4so9107358oah.11 for ; Tue, 11 Feb 2014 04:14:31 -0800 (PST) Received: from e37.co.us.ibm.com (e37.co.us.ibm.com. [32.97.110.158]) by mx.google.com with ESMTPS id kb7si9393084oeb.128.2014.02.11.04.14.31 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Tue, 11 Feb 2014 04:14:31 -0800 (PST) Received: from /spool/local by e37.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 11 Feb 2014 05:14:30 -0700 Received: from b03cxnp08028.gho.boulder.ibm.com (b03cxnp08028.gho.boulder.ibm.com [9.17.130.20]) by d03dlp03.boulder.ibm.com (Postfix) with ESMTP id C59C519D8042 for ; Tue, 11 Feb 2014 05:14:27 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp08028.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id s1BCES6s8782258 for ; Tue, 11 Feb 2014 13:14:28 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id s1BCHnwY020738 for ; Tue, 11 Feb 2014 05:17:49 -0700 Date: Tue, 11 Feb 2014 04:14:26 -0800 From: "Paul E. McKenney" Subject: Re: Memory allocator semantics Message-ID: <20140211121426.GQ4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: owner-linux-mm@kvack.org List-ID: To: Christoph Lameter Cc: Pekka Enberg , linux-mm@kvack.org, linux-kernel@vger.kernel.org, penberg@kernel.org, mpm@selenic.com On Mon, Feb 10, 2014 at 01:07:58PM -0600, Christoph Lameter wrote: > On Sat, 8 Feb 2014, Pekka Enberg wrote: > > > So to be completely honest, I don't understand what is the race in (A) that > > concerns the *memory allocator*. I also don't what the memory allocator can > > do in (B) and (C) which look like double-free and use-after-free, > > respectively, to me. :-) > > Well it seems to be some academic mind game to me. > > Does an invocation of the allocator have barrier semantics or not? In case (A), I don't see why the allocator should have barrier semantics from kmalloc() to a matching kfree(). I would argue that any needed barrier semantics must be provided by the caller. In contrast, from kfree() to a kmalloc() returning some of the kfree()ed memory, I believe the kfree()/kmalloc() implementation must do any needed synchronization and ordering. But that is a different set of examples, for example, this one: CPU 0 CPU 1 p->a = 42; q = kmalloc(...); /* returning p */ kfree(p); q->a = 5; BUG_ON(q->a != 5); Unlike the situation with (A), (B), and (C), in this case I believe that it is kfree()'s and kmalloc()'s responsibility to ensure that the BUG_ON() never triggers. Make sense? Thanx, Paul -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pd0-f172.google.com (mail-pd0-f172.google.com [209.85.192.172]) by kanga.kvack.org (Postfix) with ESMTP id 34D7F6B0031 for ; Tue, 11 Feb 2014 08:20:05 -0500 (EST) Received: by mail-pd0-f172.google.com with SMTP id p10so7532855pdj.3 for ; Tue, 11 Feb 2014 05:20:04 -0800 (PST) Received: from mail-pa0-x232.google.com (mail-pa0-x232.google.com [2607:f8b0:400e:c03::232]) by mx.google.com with ESMTPS id va10si18991676pbc.158.2014.02.11.05.20.01 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 11 Feb 2014 05:20:02 -0800 (PST) Received: by mail-pa0-f50.google.com with SMTP id kp14so7639903pab.37 for ; Tue, 11 Feb 2014 05:20:01 -0800 (PST) MIME-Version: 1.0 In-Reply-To: <20140211121426.GQ4250@linux.vnet.ibm.com> References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140211121426.GQ4250@linux.vnet.ibm.com> Date: Tue, 11 Feb 2014 15:20:01 +0200 Message-ID: Subject: Re: Memory allocator semantics From: Pekka Enberg Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Paul McKenney Cc: Christoph Lameter , "linux-mm@kvack.org" , LKML , Matt Mackall On Tue, Feb 11, 2014 at 2:14 PM, Paul E. McKenney wrote: > In contrast, from kfree() to a kmalloc() returning some of the kfree()ed > memory, I believe the kfree()/kmalloc() implementation must do any needed > synchronization and ordering. But that is a different set of examples, > for example, this one: > > CPU 0 CPU 1 > p->a = 42; q = kmalloc(...); /* returning p */ > kfree(p); q->a = 5; > BUG_ON(q->a != 5); > > Unlike the situation with (A), (B), and (C), in this case I believe > that it is kfree()'s and kmalloc()'s responsibility to ensure that > the BUG_ON() never triggers. > > Make sense? I'm not sure... It's the caller's responsibility not to touch "p" after it's handed over to kfree() - otherwise that's a "use-after-free" error. If there's some reordering going on here, I'm tempted to blame the caller for lack of locking. Pekka -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oa0-f48.google.com (mail-oa0-f48.google.com [209.85.219.48]) by kanga.kvack.org (Postfix) with ESMTP id 6F98C6B0031 for ; Tue, 11 Feb 2014 10:01:40 -0500 (EST) Received: by mail-oa0-f48.google.com with SMTP id l6so9165723oag.7 for ; Tue, 11 Feb 2014 07:01:40 -0800 (PST) Received: from e31.co.us.ibm.com (e31.co.us.ibm.com. [32.97.110.149]) by mx.google.com with ESMTPS id tk7si9659419obc.107.2014.02.11.07.01.39 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Tue, 11 Feb 2014 07:01:39 -0800 (PST) Received: from /spool/local by e31.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 11 Feb 2014 08:01:39 -0700 Received: from b03cxnp08028.gho.boulder.ibm.com (b03cxnp08028.gho.boulder.ibm.com [9.17.130.20]) by d03dlp01.boulder.ibm.com (Postfix) with ESMTP id D2A141FF003F for ; Tue, 11 Feb 2014 08:01:35 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp08028.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id s1BF1Z8I1704238 for ; Tue, 11 Feb 2014 16:01:35 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id s1BF4uK5022213 for ; Tue, 11 Feb 2014 08:04:57 -0700 Date: Tue, 11 Feb 2014 07:01:13 -0800 From: "Paul E. McKenney" Subject: Re: Memory allocator semantics Message-ID: <20140211150113.GS4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140211121426.GQ4250@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: owner-linux-mm@kvack.org List-ID: To: Pekka Enberg Cc: Christoph Lameter , "linux-mm@kvack.org" , LKML , Matt Mackall On Tue, Feb 11, 2014 at 03:20:01PM +0200, Pekka Enberg wrote: > On Tue, Feb 11, 2014 at 2:14 PM, Paul E. McKenney > wrote: > > In contrast, from kfree() to a kmalloc() returning some of the kfree()ed > > memory, I believe the kfree()/kmalloc() implementation must do any needed > > synchronization and ordering. But that is a different set of examples, > > for example, this one: > > > > CPU 0 CPU 1 > > p->a = 42; q = kmalloc(...); /* returning p */ > > kfree(p); q->a = 5; > > BUG_ON(q->a != 5); > > > > Unlike the situation with (A), (B), and (C), in this case I believe > > that it is kfree()'s and kmalloc()'s responsibility to ensure that > > the BUG_ON() never triggers. > > > > Make sense? > > I'm not sure... > > It's the caller's responsibility not to touch "p" after it's handed over to > kfree() - otherwise that's a "use-after-free" error. If there's some reordering > going on here, I'm tempted to blame the caller for lack of locking. But if the two callers are unrelated, what locking can they possibly use? >>From what I can see, the current implementation prevents the above BUG_ON() from firing. If the two CPUs are the same, the CPU will see its own accesses in order, while if they are different, the implementation will have had to push the memory through non-CPU-local data structures, which must have had some heavyweight protection. Thanx, Paul -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qc0-f176.google.com (mail-qc0-f176.google.com [209.85.216.176]) by kanga.kvack.org (Postfix) with ESMTP id D7AD06B0035 for ; Tue, 11 Feb 2014 13:43:39 -0500 (EST) Received: by mail-qc0-f176.google.com with SMTP id e16so13499973qcx.21 for ; Tue, 11 Feb 2014 10:43:39 -0800 (PST) Received: from qmta14.emeryville.ca.mail.comcast.net (qmta14.emeryville.ca.mail.comcast.net. [2001:558:fe2d:44:76:96:27:212]) by mx.google.com with ESMTP id s22si13135343qge.16.2014.02.11.10.43.38 for ; Tue, 11 Feb 2014 10:43:38 -0800 (PST) Date: Tue, 11 Feb 2014 12:43:35 -0600 (CST) From: Christoph Lameter Subject: Re: Memory allocator semantics In-Reply-To: Message-ID: References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140209020004.GY4250@linux.vnet.ibm.com> Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-linux-mm@kvack.org List-ID: To: Pekka Enberg Cc: Paul McKenney , "linux-mm@kvack.org" , LKML , Matt Mackall On Tue, 11 Feb 2014, Pekka Enberg wrote: > So again, there's nothing in (A) that the memory allocator is > concerned about. kmalloc() makes no guarantees whatsoever about the > visibility of "r1" across CPUs. If you're saying that there's an > implicit barrier between kmalloc() and kfree(), that's an unintended > side-effect, not a design decision AFAICT. I am not sure that this side effect necessarily happens. The SLUB fastpath does not disable interrupts and only uses a cmpxchg without lock semantics. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qa0-f41.google.com (mail-qa0-f41.google.com [209.85.216.41]) by kanga.kvack.org (Postfix) with ESMTP id 69FC06B0031 for ; Fri, 14 Feb 2014 12:30:56 -0500 (EST) Received: by mail-qa0-f41.google.com with SMTP id w8so18922707qac.0 for ; Fri, 14 Feb 2014 09:30:56 -0800 (PST) Received: from e36.co.us.ibm.com (e36.co.us.ibm.com. [32.97.110.154]) by mx.google.com with ESMTPS id j4si4321822qao.24.2014.02.14.09.30.54 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Fri, 14 Feb 2014 09:30:55 -0800 (PST) Received: from /spool/local by e36.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Fri, 14 Feb 2014 10:30:54 -0700 Received: from b03cxnp07028.gho.boulder.ibm.com (b03cxnp07028.gho.boulder.ibm.com [9.17.130.15]) by d03dlp02.boulder.ibm.com (Postfix) with ESMTP id ED5243E4003F for ; Fri, 14 Feb 2014 10:30:51 -0700 (MST) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by b03cxnp07028.gho.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id s1EHUOqN3080582 for ; Fri, 14 Feb 2014 18:30:24 +0100 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id s1EHYEhw011354 for ; Fri, 14 Feb 2014 10:34:14 -0700 Date: Fri, 14 Feb 2014 09:30:39 -0800 From: "Paul E. McKenney" Subject: Re: Memory allocator semantics Message-ID: <20140214173038.GR4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140209020004.GY4250@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: owner-linux-mm@kvack.org List-ID: To: Christoph Lameter Cc: Pekka Enberg , "linux-mm@kvack.org" , LKML , Matt Mackall On Tue, Feb 11, 2014 at 12:43:35PM -0600, Christoph Lameter wrote: > On Tue, 11 Feb 2014, Pekka Enberg wrote: > > > So again, there's nothing in (A) that the memory allocator is > > concerned about. kmalloc() makes no guarantees whatsoever about the > > visibility of "r1" across CPUs. If you're saying that there's an > > implicit barrier between kmalloc() and kfree(), that's an unintended > > side-effect, not a design decision AFAICT. > > I am not sure that this side effect necessarily happens. The SLUB fastpath > does not disable interrupts and only uses a cmpxchg without lock > semantics. That tells me what I need to know. Users should definitely not try a "drive-by kfree()" of something that was concurrently allocated. ;-) Thanx, Paul -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752531AbaABUdl (ORCPT ); Thu, 2 Jan 2014 15:33:41 -0500 Received: from e37.co.us.ibm.com ([32.97.110.158]:58770 "EHLO e37.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751841AbaABUdk (ORCPT ); Thu, 2 Jan 2014 15:33:40 -0500 Date: Thu, 2 Jan 2014 12:33:20 -0800 From: "Paul E. McKenney" To: linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Subject: Memory allocator semantics Message-ID: <20140102203320.GA27615@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 14010220-7164-0000-0000-000004C6FE58 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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: B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); This results in the memory being on two different freelists. C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; This results in the memory being used by two different CPUs, each of which believe that they have sole access. 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? Thanx, Paul PS. To the question "Why would anyone care about (A)?", then answer is "Inquiring programming-language memory-model designers want to know." From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753109AbaACDjS (ORCPT ); Thu, 2 Jan 2014 22:39:18 -0500 Received: from relay3-d.mail.gandi.net ([217.70.183.195]:39781 "EHLO relay3-d.mail.gandi.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750743AbaACDjR (ORCPT ); Thu, 2 Jan 2014 22:39:17 -0500 X-Originating-IP: 50.43.14.201 Date: Thu, 2 Jan 2014 19:39:07 -0800 From: Josh Triplett To: "Paul E. McKenney" Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics Message-ID: <20140103033906.GB2983@leaf> References: <20140102203320.GA27615@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20140102203320.GA27615@linux.vnet.ibm.com> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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. > B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > This results in the memory being on two different freelists. That's a straightforward double-free bug. You need some kind of synchronization there to ensure that only one call to kfree occurs. > C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; > > This results in the memory being used by two different CPUs, > each of which believe that they have sole access. This is not OK either: CPU 2 has called kfree on a pointer that CPU 1 still considers alive, and again, the CPUs haven't used any form of synchronization to prevent that. > 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. > 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. - Josh Triplett From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1750820AbaACFOk (ORCPT ); Fri, 3 Jan 2014 00:14:40 -0500 Received: from e32.co.us.ibm.com ([32.97.110.150]:32942 "EHLO e32.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750717AbaACFOj (ORCPT ); Fri, 3 Jan 2014 00:14:39 -0500 Date: Thu, 2 Jan 2014 21:14:17 -0800 From: "Paul E. McKenney" To: Josh Triplett Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics Message-ID: <20140103051417.GT19211@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <20140103033906.GB2983@leaf> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20140103033906.GB2983@leaf> User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 14010305-0928-0000-0000-0000054252C1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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. And the fact that slab/slob/slub seem to handle (A) seemed bizarre enough to be worth asking the question. > > B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > > > CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); > > > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > > > This results in the memory being on two different freelists. > > That's a straightforward double-free bug. You need some kind of > synchronization there to ensure that only one call to kfree occurs. Yep! > > C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > > > CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; > > > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > > > CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; > > > > This results in the memory being used by two different CPUs, > > each of which believe that they have sole access. > > This is not OK either: CPU 2 has called kfree on a pointer that CPU 1 > still considers alive, and again, the CPUs haven't used any form of > synchronization to prevent that. Agreed. > > 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(). ;-) > > 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). 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.) Thanx, Paul From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751236AbaACFrj (ORCPT ); Fri, 3 Jan 2014 00:47:39 -0500 Received: from relay3-d.mail.gandi.net ([217.70.183.195]:40038 "EHLO relay3-d.mail.gandi.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751096AbaACFrM convert rfc822-to-8bit (ORCPT ); Fri, 3 Jan 2014 00:47:12 -0500 X-Originating-IP: 50.43.14.201 Date: Thu, 2 Jan 2014 21:47:00 -0800 From: Josh Triplett To: "Paul E. McKenney" Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics Message-ID: <20140103054700.GA4865@leaf> References: <20140102203320.GA27615@linux.vnet.ibm.com> <20140103033906.GB2983@leaf> <20140103051417.GT19211@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20140103051417.GT19211@linux.vnet.ibm.com> User-Agent: Mutt/1.5.21 (2010-09-15) Content-Transfer-Encoding: 8BIT Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751544AbaACH5q (ORCPT ); Fri, 3 Jan 2014 02:57:46 -0500 Received: from e33.co.us.ibm.com ([32.97.110.151]:57866 "EHLO e33.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750862AbaACH5p (ORCPT ); Fri, 3 Jan 2014 02:57:45 -0500 Date: Thu, 2 Jan 2014 23:57:27 -0800 From: "Paul E. McKenney" To: Josh Triplett Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics Message-ID: <20140103075727.GU19211@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <20140103033906.GB2983@leaf> <20140103051417.GT19211@linux.vnet.ibm.com> <20140103054700.GA4865@leaf> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20140103054700.GA4865@leaf> User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 14010307-0928-0000-0000-0000050E2DAC Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751459AbaACImq (ORCPT ); Fri, 3 Jan 2014 03:42:46 -0500 Received: from relay3-d.mail.gandi.net ([217.70.183.195]:44501 "EHLO relay3-d.mail.gandi.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750853AbaACImo convert rfc822-to-8bit (ORCPT ); Fri, 3 Jan 2014 03:42:44 -0500 X-Originating-IP: 50.43.14.201 Date: Fri, 3 Jan 2014 00:42:36 -0800 From: Josh Triplett To: "Paul E. McKenney" Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics Message-ID: <20140103084236.GA5992@leaf> References: <20140102203320.GA27615@linux.vnet.ibm.com> <20140103033906.GB2983@leaf> <20140103051417.GT19211@linux.vnet.ibm.com> <20140103054700.GA4865@leaf> <20140103075727.GU19211@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20140103075727.GU19211@linux.vnet.ibm.com> User-Agent: Mutt/1.5.21 (2010-09-15) Content-Transfer-Encoding: 8BIT Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, Jan 02, 2014 at 11:57:27PM -0800, Paul E. McKenney wrote: > 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." Gah. That doesn't seem like a memory-ordering guarantee the allocator should have to provide for its caller, and I can easily think of allocator structures that wouldn't guarantee it without the inclusion of an explicit memory barrier. (Also, I assume the last use of "block" in that sentence should have been "byte"?) > > - 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. I *think* that's the right formal relationship I'm suggesting, yes. Mostly I'm suggesting that since the only sensible way for the pointer value you're passing to free to have come into existence is to have received it from malloc at some point in the past (as opposed to magically divining its value), it's not so much "requiring the user to have a happens-before relationship" as "not allowing the user to randomly make up pointers and free them, even if they happen to match the value being returned from a concurrent malloc". Because that's the only way I can think of for malloc and free to race on the same pointer. In any case, let me know if the rules sketched above end up proving useful as part of the requirements for malloc/free. - Josh Triplett From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751622AbaBHK1l (ORCPT ); Sat, 8 Feb 2014 05:27:41 -0500 Received: from out4-smtp.messagingengine.com ([66.111.4.28]:50370 "EHLO out4-smtp.messagingengine.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751063AbaBHK1j (ORCPT ); Sat, 8 Feb 2014 05:27:39 -0500 X-Sasl-enc: uaWdfH38Smv11IXh7+Ghxoc5Hf/SHJ62ES2zIf1VcOge 1391855258 Message-ID: <52F60699.8010204@iki.fi> Date: Sat, 08 Feb 2014 12:27:37 +0200 From: Pekka Enberg User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0 MIME-Version: 1.0 To: paulmck@linux.vnet.ibm.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org CC: cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics References: <20140102203320.GA27615@linux.vnet.ibm.com> In-Reply-To: <20140102203320.GA27615@linux.vnet.ibm.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi Paul, On 01/02/2014 10:33 PM, Paul E. McKenney wrote: > 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: > > B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > This results in the memory being on two different freelists. > > C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; > > This results in the memory being used by two different CPUs, > each of which believe that they have sole access. > > 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? So to be completely honest, I don't understand what is the race in (A) that concerns the *memory allocator*. I also don't what the memory allocator can do in (B) and (C) which look like double-free and use-after-free, respectively, to me. :-) Pekka From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751570AbaBICAN (ORCPT ); Sat, 8 Feb 2014 21:00:13 -0500 Received: from e34.co.us.ibm.com ([32.97.110.152]:46365 "EHLO e34.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751501AbaBICAL (ORCPT ); Sat, 8 Feb 2014 21:00:11 -0500 Date: Sat, 8 Feb 2014 18:00:04 -0800 From: "Paul E. McKenney" To: Pekka Enberg Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux-foundation.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics Message-ID: <20140209020004.GY4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <52F60699.8010204@iki.fi> User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 14020902-1542-0000-0000-000005E980D1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sat, Feb 08, 2014 at 12:27:37PM +0200, Pekka Enberg wrote: > Hi Paul, > > On 01/02/2014 10:33 PM, Paul E. McKenney wrote: > > 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: > > > >B. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > > > CPU 1: r2 = ACCESS_ONCE(shared_x); if (r2) kfree(r2); > > > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > > > This results in the memory being on two different freelists. > > > >C. CPU 0: r1 = kmalloc(...); ACCESS_ONCE(shared_x) = r1; > > > > CPU 1: r2 = ACCESS_ONCE(shared_x); r2->a = 1; r2->b = 2; > > > > CPU 2: r3 = ACCESS_ONCE(shared_x); if (r3) kfree(r3); > > > > CPU 3: r4 = kmalloc(...); r4->s = 3; r4->t = 4; > > > > This results in the memory being used by two different CPUs, > > each of which believe that they have sole access. > > > >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? > > So to be completely honest, I don't understand what is the race in > (A) that concerns the *memory allocator*. I also don't what the > memory allocator can do in (B) and (C) which look like double-free > and use-after-free, respectively, to me. :-) >>From what I can see, (A) works by accident, but is kind of useless because you allocate and free the memory without touching it. (B) and (C) are the lightest touches I could imagine, and as you say, both are bad. So I believe that it is reasonable to prohibit (A). Or is there some use for (A) that I am missing? Thanx, Paul From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752781AbaBJTIE (ORCPT ); Mon, 10 Feb 2014 14:08:04 -0500 Received: from qmta03.emeryville.ca.mail.comcast.net ([76.96.30.32]:53089 "EHLO qmta03.emeryville.ca.mail.comcast.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751807AbaBJTIB (ORCPT ); Mon, 10 Feb 2014 14:08:01 -0500 Date: Mon, 10 Feb 2014 13:07:58 -0600 (CST) From: Christoph Lameter X-X-Sender: cl@nuc To: Pekka Enberg cc: paulmck@linux.vnet.ibm.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics In-Reply-To: <52F60699.8010204@iki.fi> Message-ID: References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sat, 8 Feb 2014, Pekka Enberg wrote: > So to be completely honest, I don't understand what is the race in (A) that > concerns the *memory allocator*. I also don't what the memory allocator can > do in (B) and (C) which look like double-free and use-after-free, > respectively, to me. :-) Well it seems to be some academic mind game to me. Does an invocation of the allocator have barrier semantics or not? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751709AbaBKIu3 (ORCPT ); Tue, 11 Feb 2014 03:50:29 -0500 Received: from mail-pb0-f47.google.com ([209.85.160.47]:47393 "EHLO mail-pb0-f47.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751514AbaBKIuZ (ORCPT ); Tue, 11 Feb 2014 03:50:25 -0500 MIME-Version: 1.0 In-Reply-To: <20140209020004.GY4250@linux.vnet.ibm.com> References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140209020004.GY4250@linux.vnet.ibm.com> Date: Tue, 11 Feb 2014 10:50:24 +0200 X-Google-Sender-Auth: ibqmimNeL75kB0ByOsTr0usXRcs Message-ID: Subject: Re: Memory allocator semantics From: Pekka Enberg To: Paul McKenney Cc: "linux-mm@kvack.org" , LKML , Christoph Lameter , Matt Mackall Content-Type: text/plain; charset=ISO-8859-1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi Paul, On Sun, Feb 9, 2014 at 4:00 AM, Paul E. McKenney wrote: > From what I can see, (A) works by accident, but is kind of useless because > you allocate and free the memory without touching it. (B) and (C) are the > lightest touches I could imagine, and as you say, both are bad. So I > believe that it is reasonable to prohibit (A). > > Or is there some use for (A) that I am missing? So again, there's nothing in (A) that the memory allocator is concerned about. kmalloc() makes no guarantees whatsoever about the visibility of "r1" across CPUs. If you're saying that there's an implicit barrier between kmalloc() and kfree(), that's an unintended side-effect, not a design decision AFAICT. Pekka From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751656AbaBKMJY (ORCPT ); Tue, 11 Feb 2014 07:09:24 -0500 Received: from e33.co.us.ibm.com ([32.97.110.151]:35339 "EHLO e33.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750758AbaBKMJW (ORCPT ); Tue, 11 Feb 2014 07:09:22 -0500 Date: Tue, 11 Feb 2014 04:09:16 -0800 From: "Paul E. McKenney" To: Pekka Enberg Cc: "linux-mm@kvack.org" , LKML , Christoph Lameter , Matt Mackall Subject: Re: Memory allocator semantics Message-ID: <20140211120915.GP4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140209020004.GY4250@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 14021112-0928-0000-0000-00000636B502 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Feb 11, 2014 at 10:50:24AM +0200, Pekka Enberg wrote: > Hi Paul, > > On Sun, Feb 9, 2014 at 4:00 AM, Paul E. McKenney > wrote: > > From what I can see, (A) works by accident, but is kind of useless because > > you allocate and free the memory without touching it. (B) and (C) are the > > lightest touches I could imagine, and as you say, both are bad. So I > > believe that it is reasonable to prohibit (A). > > > > Or is there some use for (A) that I am missing? > > So again, there's nothing in (A) that the memory allocator is > concerned about. kmalloc() makes no guarantees whatsoever about the > visibility of "r1" across CPUs. If you're saying that there's an > implicit barrier between kmalloc() and kfree(), that's an unintended > side-effect, not a design decision AFAICT. Thank you. That was what I suspected, and I believe that it is a completely reasonable response to (A). Thanx, Paul From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751756AbaBKMOe (ORCPT ); Tue, 11 Feb 2014 07:14:34 -0500 Received: from e32.co.us.ibm.com ([32.97.110.150]:51958 "EHLO e32.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751004AbaBKMOb (ORCPT ); Tue, 11 Feb 2014 07:14:31 -0500 Date: Tue, 11 Feb 2014 04:14:26 -0800 From: "Paul E. McKenney" To: Christoph Lameter Cc: Pekka Enberg , linux-mm@kvack.org, linux-kernel@vger.kernel.org, penberg@kernel.org, mpm@selenic.com Subject: Re: Memory allocator semantics Message-ID: <20140211121426.GQ4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 14021112-0928-0000-0000-0000067CF7AC Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Feb 10, 2014 at 01:07:58PM -0600, Christoph Lameter wrote: > On Sat, 8 Feb 2014, Pekka Enberg wrote: > > > So to be completely honest, I don't understand what is the race in (A) that > > concerns the *memory allocator*. I also don't what the memory allocator can > > do in (B) and (C) which look like double-free and use-after-free, > > respectively, to me. :-) > > Well it seems to be some academic mind game to me. > > Does an invocation of the allocator have barrier semantics or not? In case (A), I don't see why the allocator should have barrier semantics from kmalloc() to a matching kfree(). I would argue that any needed barrier semantics must be provided by the caller. In contrast, from kfree() to a kmalloc() returning some of the kfree()ed memory, I believe the kfree()/kmalloc() implementation must do any needed synchronization and ordering. But that is a different set of examples, for example, this one: CPU 0 CPU 1 p->a = 42; q = kmalloc(...); /* returning p */ kfree(p); q->a = 5; BUG_ON(q->a != 5); Unlike the situation with (A), (B), and (C), in this case I believe that it is kfree()'s and kmalloc()'s responsibility to ensure that the BUG_ON() never triggers. Make sense? Thanx, Paul From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751886AbaBKNUE (ORCPT ); Tue, 11 Feb 2014 08:20:04 -0500 Received: from mail-pd0-f182.google.com ([209.85.192.182]:35306 "EHLO mail-pd0-f182.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751053AbaBKNUC (ORCPT ); Tue, 11 Feb 2014 08:20:02 -0500 MIME-Version: 1.0 In-Reply-To: <20140211121426.GQ4250@linux.vnet.ibm.com> References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140211121426.GQ4250@linux.vnet.ibm.com> Date: Tue, 11 Feb 2014 15:20:01 +0200 X-Google-Sender-Auth: cDBYYvMInj7uKHFLtJI6vrjdwEE Message-ID: Subject: Re: Memory allocator semantics From: Pekka Enberg To: Paul McKenney Cc: Christoph Lameter , "linux-mm@kvack.org" , LKML , Matt Mackall Content-Type: text/plain; charset=ISO-8859-1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Feb 11, 2014 at 2:14 PM, Paul E. McKenney wrote: > In contrast, from kfree() to a kmalloc() returning some of the kfree()ed > memory, I believe the kfree()/kmalloc() implementation must do any needed > synchronization and ordering. But that is a different set of examples, > for example, this one: > > CPU 0 CPU 1 > p->a = 42; q = kmalloc(...); /* returning p */ > kfree(p); q->a = 5; > BUG_ON(q->a != 5); > > Unlike the situation with (A), (B), and (C), in this case I believe > that it is kfree()'s and kmalloc()'s responsibility to ensure that > the BUG_ON() never triggers. > > Make sense? I'm not sure... It's the caller's responsibility not to touch "p" after it's handed over to kfree() - otherwise that's a "use-after-free" error. If there's some reordering going on here, I'm tempted to blame the caller for lack of locking. Pekka From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751956AbaBKPBl (ORCPT ); Tue, 11 Feb 2014 10:01:41 -0500 Received: from e31.co.us.ibm.com ([32.97.110.149]:38203 "EHLO e31.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751105AbaBKPBj (ORCPT ); Tue, 11 Feb 2014 10:01:39 -0500 Date: Tue, 11 Feb 2014 07:01:13 -0800 From: "Paul E. McKenney" To: Pekka Enberg Cc: Christoph Lameter , "linux-mm@kvack.org" , LKML , Matt Mackall Subject: Re: Memory allocator semantics Message-ID: <20140211150113.GS4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140211121426.GQ4250@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 14021115-8236-0000-0000-000006F7B511 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Feb 11, 2014 at 03:20:01PM +0200, Pekka Enberg wrote: > On Tue, Feb 11, 2014 at 2:14 PM, Paul E. McKenney > wrote: > > In contrast, from kfree() to a kmalloc() returning some of the kfree()ed > > memory, I believe the kfree()/kmalloc() implementation must do any needed > > synchronization and ordering. But that is a different set of examples, > > for example, this one: > > > > CPU 0 CPU 1 > > p->a = 42; q = kmalloc(...); /* returning p */ > > kfree(p); q->a = 5; > > BUG_ON(q->a != 5); > > > > Unlike the situation with (A), (B), and (C), in this case I believe > > that it is kfree()'s and kmalloc()'s responsibility to ensure that > > the BUG_ON() never triggers. > > > > Make sense? > > I'm not sure... > > It's the caller's responsibility not to touch "p" after it's handed over to > kfree() - otherwise that's a "use-after-free" error. If there's some reordering > going on here, I'm tempted to blame the caller for lack of locking. But if the two callers are unrelated, what locking can they possibly use? >>From what I can see, the current implementation prevents the above BUG_ON() from firing. If the two CPUs are the same, the CPU will see its own accesses in order, while if they are different, the implementation will have had to push the memory through non-CPU-local data structures, which must have had some heavyweight protection. Thanx, Paul From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751840AbaBKSn5 (ORCPT ); Tue, 11 Feb 2014 13:43:57 -0500 Received: from qmta08.emeryville.ca.mail.comcast.net ([76.96.30.80]:57138 "EHLO qmta08.emeryville.ca.mail.comcast.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751656AbaBKSni (ORCPT ); Tue, 11 Feb 2014 13:43:38 -0500 Date: Tue, 11 Feb 2014 12:43:35 -0600 (CST) From: Christoph Lameter X-X-Sender: cl@nuc To: Pekka Enberg cc: Paul McKenney , "linux-mm@kvack.org" , LKML , Matt Mackall Subject: Re: Memory allocator semantics In-Reply-To: Message-ID: References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140209020004.GY4250@linux.vnet.ibm.com> Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, 11 Feb 2014, Pekka Enberg wrote: > So again, there's nothing in (A) that the memory allocator is > concerned about. kmalloc() makes no guarantees whatsoever about the > visibility of "r1" across CPUs. If you're saying that there's an > implicit barrier between kmalloc() and kfree(), that's an unintended > side-effect, not a design decision AFAICT. I am not sure that this side effect necessarily happens. The SLUB fastpath does not disable interrupts and only uses a cmpxchg without lock semantics. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752583AbaBNRa6 (ORCPT ); Fri, 14 Feb 2014 12:30:58 -0500 Received: from e37.co.us.ibm.com ([32.97.110.158]:55084 "EHLO e37.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752432AbaBNRa4 (ORCPT ); Fri, 14 Feb 2014 12:30:56 -0500 Date: Fri, 14 Feb 2014 09:30:39 -0800 From: "Paul E. McKenney" To: Christoph Lameter Cc: Pekka Enberg , "linux-mm@kvack.org" , LKML , Matt Mackall Subject: Re: Memory allocator semantics Message-ID: <20140214173038.GR4250@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20140102203320.GA27615@linux.vnet.ibm.com> <52F60699.8010204@iki.fi> <20140209020004.GY4250@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 14021417-7164-0000-0000-00000608205D Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Feb 11, 2014 at 12:43:35PM -0600, Christoph Lameter wrote: > On Tue, 11 Feb 2014, Pekka Enberg wrote: > > > So again, there's nothing in (A) that the memory allocator is > > concerned about. kmalloc() makes no guarantees whatsoever about the > > visibility of "r1" across CPUs. If you're saying that there's an > > implicit barrier between kmalloc() and kfree(), that's an unintended > > side-effect, not a design decision AFAICT. > > I am not sure that this side effect necessarily happens. The SLUB fastpath > does not disable interrupts and only uses a cmpxchg without lock > semantics. That tells me what I need to know. Users should definitely not try a "drive-by kfree()" of something that was concurrently allocated. ;-) Thanx, Paul