Received: by 10.192.165.148 with SMTP id m20csp3502678imm; Mon, 7 May 2018 13:28:28 -0700 (PDT) X-Google-Smtp-Source: AB8JxZqzVcUREWCoYBjNiSPjnsfQU9C1pQbAweytyagWsp2qKRAJzx99NbiVGSayjJ75050mDskw X-Received: by 2002:a9d:250c:: with SMTP id k12-v6mr28844107otb.362.1525724908556; Mon, 07 May 2018 13:28:28 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1525724908; cv=none; d=google.com; s=arc-20160816; b=Bwdby1hWOL2AMyQ5WpfScY8GAVy6+izKiK5bPYjTWQAS2E916s/Cl9XwmRichKGwJ+ OlhhwvQMlM1vEAJsg8ws5ZRCyTLo/Efuw7EDFw8KT5QjJ7NuY/uhok/OOQHvaPy1gyq5 Ryq8Ru0lvgbcM4ee29B+2tDWG6oXGbIrqHTFJH1mMRO8xwGbQQmzOJZA9L6YfltXhwpo 1qzAbLzQVRUP6q5CY0a76S7FEsGVznntSU/FDjCQDzGlUicdEKnFuD1ivZ93TDx26JMH EIqfrv/YakEjc4n/3DSaA5ZpHp9LUG5X7bKeVPvIdzevQNjMTncIRv0xVILsWwcz+WBt OtiA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:cc:to:subject:message-id:date:from :references:in-reply-to:mime-version:dkim-signature :arc-authentication-results; bh=XCFPrlGIEX0v+9YtFAMvGY6MsTS2ENu3QpuSrQnxOQs=; b=s5SGKI0p6zLbnINW+BDQbiV8KfaGAEvzg2lrogyKF/weEBfPTKMz4Vlp/CU/qL4GKv tTjFGtueLXWirAJclC2w4UhOdkz1fhmfculbpjovzMiIrP49SBoh+RfLDlvYX6rAWBuO 2oUHf8Pi0YJcMTaOX7cKj36HCFLDaSdtyGFprXrWW7QL1mYgHEyuODZjf4hRv21BEkN6 PfBqUQw/XtCVa3cKv9l0RDufbFioWCy76JGpIWhjz9epmnpYXXDGNCJPD776xwFWDXOU /Q2oQlTB9LOe6cUpvG5flBpQ5BJhW3I+xkCeInBUxkGhLMruD6AqZmQNqw0aUfUI3VtD XmoA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=rhWULM2m; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id 18-v6si5737422ote.298.2018.05.07.13.28.14; Mon, 07 May 2018 13:28:28 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=rhWULM2m; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752754AbeEGU1m (ORCPT + 99 others); Mon, 7 May 2018 16:27:42 -0400 Received: from mail-vk0-f53.google.com ([209.85.213.53]:39120 "EHLO mail-vk0-f53.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752389AbeEGU1k (ORCPT ); Mon, 7 May 2018 16:27:40 -0400 Received: by mail-vk0-f53.google.com with SMTP id g83-v6so18289688vkc.6 for ; Mon, 07 May 2018 13:27:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=XCFPrlGIEX0v+9YtFAMvGY6MsTS2ENu3QpuSrQnxOQs=; b=rhWULM2mvj8RT3lC6+dtmVZWWS5gO9MNvuEhermwuZ93mnAI2v023vR/ERwn2GcoaA K0ndtrAmDZuuErlL+Dzj6l2b8ktWcOIluDE1DPnOXzMi0porwxegX3mvXQRXAhw7Ikt9 zR8KkFxvbJwmA0ipERF451kZKTPrhh/Sc/bBFYG5HfiX5oNSzPh+UTht8USCrwc8rHvB 0LjCqrv4LSyzDvh+ALu01/vq+Zyy0VnkNqKq/YaDlJ1UeJ/hE+McCgucqSPK6Vqy/rF9 czYAh0DG/42w44PfBab8BJQLi71bhNES5Zm02Q/esSUIdZpKB1qwyER9/yDKnBfDN2QG 0oQw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=XCFPrlGIEX0v+9YtFAMvGY6MsTS2ENu3QpuSrQnxOQs=; b=mxkyVFuMb7Cb9tV2TKX4fsOKW8wARfZ4tauVhDYOrJ46Iv99UXiSsjm1j9F9C08NYN e4gLymp2H7qHcUNEW1WU6wcwHJRqFAETMQG6xzHa09DS966bz34/JnU6o5kH4fyLHo3q 2ZjaeZaO53zAQafA+jDbgeeSss4g9KDNnE60dpQ7CLduNu4lRIpjzwpwDeM/xWmN2gvS 11yZkWGilaQDzUduxUpWYSoCCA0chsaeSUYTFdqY/o/LCP+HHO1njtTYuS+nH+Kgam8R eRjWw2XMN1yIpEMxsZWkIEd1jvRFwpKapLBsHixCz3DgMIeq+jpxxplissKBNPNo0XA+ Guag== X-Gm-Message-State: ALQs6tDsHpFrEM8xZ2LIqYljR83maJSGIr72rBbQKAJUzPKLw3acf58c 7cREMmVET1EHy4fZfz3n9P+nKtKZ/aLoz3OCUklDOA== X-Received: by 2002:a1f:b9d2:: with SMTP id j201-v6mr32365201vkf.123.1525724859583; Mon, 07 May 2018 13:27:39 -0700 (PDT) MIME-Version: 1.0 Received: by 10.31.11.209 with HTTP; Mon, 7 May 2018 13:27:38 -0700 (PDT) In-Reply-To: <20180507201945.GB15604@bombadil.infradead.org> References: <20180505034646.GA20495@bombadil.infradead.org> <20180507113902.GC18116@bombadil.infradead.org> <20180507201945.GB15604@bombadil.infradead.org> From: Kees Cook Date: Mon, 7 May 2018 13:27:38 -0700 Message-ID: Subject: Re: *alloc API changes To: Matthew Wilcox , John Johansen Cc: Matthew Wilcox , Linux-MM , LKML , Rasmus Villemoes Content-Type: text/plain; charset="UTF-8" Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, May 7, 2018 at 1:19 PM, Matthew Wilcox wrote: > On Mon, May 07, 2018 at 09:03:54AM -0700, Kees Cook wrote: >> On Mon, May 7, 2018 at 4:39 AM, Matthew Wilcox wrote: >> > On Fri, May 04, 2018 at 09:24:56PM -0700, Kees Cook wrote: >> >> On Fri, May 4, 2018 at 8:46 PM, Matthew Wilcox wrote: >> >> The only fear I have with the saturating helpers is that we'll end up >> >> using them in places that don't recognize SIZE_MAX. Like, say: >> >> >> >> size = mul(a, b) + 1; >> >> >> >> then *poof* size == 0. Now, I'd hope that code would use add(mul(a, >> >> b), 1), but still... it makes me nervous. >> > >> > That's reasonable. So let's add: >> > >> > #define ALLOC_TOO_BIG (PAGE_SIZE << MAX_ORDER) >> > >> > (there's a presumably somewhat obsolete CONFIG_FORCE_MAX_ZONEORDER on some >> > architectures which allows people to configure MAX_ORDER all the way up >> > to 64. That config option needs to go away, or at least be limited to >> > a much lower value). >> > >> > On x86, that's 4k << 11 = 8MB. On PPC, that might be 64k << 9 == 32MB. >> > Those values should be relatively immune to further arithmetic causing >> > an additional overflow. >> >> But we can do larger than 8MB allocations with vmalloc, can't we? > > Yes. And today with kvmalloc. However, I proposed to Linus that > kvmalloc() shouldn't allow it -- we should have kvmalloc_large() which > would, but kvmalloc wouldn't. He liked that idea, so I'm going with it. How would we handle size calculations for _large? > There are very, very few places which should need kvmalloc_large. > That's one million 8-byte pointers. If you need more than that inside > the kernel, you're doing something really damn weird and should do > something that looks obviously different. I'm CCing John since I remember long ago running into problems loading the AppArmor DFA with kmalloc and switching it to kvmalloc. John, how large can the DFAs for AppArmor get? Would an 8MB limit be a problem? And do we have any large IO or network buffers >8MB? >> > I don't think it should go in the callers though ... where it goes in >> > the allocator is up to the allocator maintainers ;-) >> >> We need a self-test regardless, so checking that each allocator >> returns NULL with the saturated value can be done. > > Yes, absolutely. > >> >> > I'd rather have a mul_ab(), mul_abc(), mul_ab_add_c(), etc. than nest >> >> > calls to mult(). >> >> >> >> Agreed. I think having exactly those would cover almost everything, >> >> and the two places where a 4-factor product is needed could just nest >> >> them. (bikeshed: the very common mul_ab() should just be mul(), IMO.) >> >> >> >> > Nono, Linus had the better proposal, struct_size(p, member, n). >> >> >> >> Oh, yes! I totally missed that in the threads. >> > >> > so we're agreed on struct_size(). I think rather than the explicit 'mul', >> > perhaps we should have array_size() and array3_size(). >> >> I do like the symmetry there. My earlier "what if someone does +1" >> continues to scratch at my brain, though I think it's likely >> unimportant: there's no indication (in the name) that these calls >> saturate. Will someone ever do something crazy like: array_size(a, b) >> / array_size(c, d) and they can, effectively, a truncated value (if >> "a, b" saturated and "c, d" didn't...)? > > Without CPU support for a saturated value, there's no "safe" saturated > value. You can always come up with some arithmetic that will bring it > back into the valid range. All we can do is go "large enough" and hope. > >> >> Right, no. I think if we can ditch *calloc() and _array() by using >> >> saturating helpers, we'll have the API in a much better form: >> >> >> >> kmalloc(foo * bar, GFP_KERNEL); >> >> into >> >> kmalloc_array(foo, bar, GFP_KERNEL); >> >> into >> >> kmalloc(mul(foo, bar), GFP_KERNEL); >> > >> > kmalloc(array_size(foo, bar), GFP_KERNEL); >> >> I can't come up with a better name. :P When it was "mul()" I was >> thinking "smul()" for "saturating multiply". sarray_size() seems ... >> bonkers. > > smul would mean 'signed multiply' to me, having read the GCC manual: > -- Built-in Function: bool __builtin_smul_overflow (int a, int b, int *res) > > but I thought of another problem with array_size. We already have > ARRAY_SIZE and it means "the number of elements in the array". > > so ... struct_bytes(), array_bytes(), array3_bytes()? Maybe "calc"? struct_calc(), array_calc(), array3_calc()? This has the benefit of actually saying more about what it is doing, rather than its return value... In the end, I don't care. :) >> > I think we're broadly in agreement here! >> >> Do we want addition helpers? (And division and subtraction?) > > Keeping our focus on allocations ... do we have plain additions (as > opposed to multiply-and-add?) And subtraction? All I've seen are just rare "weird" cases of lots of mult/add. Some are way worse than others: http://www.ozlabs.org/~akpm/mmotm/broken-out/exofs-avoid-vla-in-structures.patch Just having the mult/add saturation would be lovely. -Kees -- Kees Cook Pixel Security