Received: by 10.192.165.148 with SMTP id m20csp3567060imm; Mon, 7 May 2018 14:41:55 -0700 (PDT) X-Google-Smtp-Source: AB8JxZoP/+gNXdyY2a/k5bt6YLHahLyO0W6Aay5UDgBQOVJKOli0qOTjJNVaTi0s47PBACPgbrVl X-Received: by 2002:a63:b94a:: with SMTP id v10-v6mr30797182pgo.372.1525729315868; Mon, 07 May 2018 14:41:55 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1525729315; cv=none; d=google.com; s=arc-20160816; b=oGS9It1LqWc0c/D4xYEGGlwavAXPw6B1XLyJGdZAj+fRVCyZgZzyrM/F7Nmdo+eIk2 YDZCgVeLuPf927DNYHf8mumVO7yc8w7TLfUDW1SZV8OJzC3DeEnzzeC1OoBvHpJmqFcH 9ZqBgKzLHAONaD6uA73P4k75Bc3dEGWk58Z+ucRK7ctGKl5SDlb6Tf5xwzeyqTVmGlsz NMdIzuJ/+vWksExre4Zcesho0crbrk4vrlOprY1XIaBm2Nzu9iPCQOBu01KPcMM1zE5Z FlCTANSsK8TL8OvOD6nMLISXEdPoBziG04PnCHNR9ZpiBSmJrOpDCFZnDVbC2xQJbJee D6dw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:content-transfer-encoding :content-language:in-reply-to:mime-version:user-agent:date :message-id:from:references:cc:to:subject:dkim-signature :arc-authentication-results; bh=F0oLgBS4P7DLBDMcIH0OIfsGB5c7ApmDBVO/j7xM6l0=; b=zYKiOkfCgHoeiQhEczUXpqEGHxbQQoZDD2wGJLDcVwbsz4DSScyRxa9U+SzKkcJGZI 49TsuqLWS9TC4HSuYNn3aThllLQKv+eCdJKB5EJEyZ33VKtDZz9MdUwKu1hgNjkKkmUx DF8sTm0jm5t9em7Vbm9QzG7rdd52Gp3+GMaHFLFK/Z9hmKIO22YoBGGniMPNWV/4iK6i Mjm3rY82IKCnsJ27E9GpDXybayRlpuNaHvHytzTMxtwY4C8eDgoOI2Hz8dZLgkCURAj3 h6DYSG95pbWgInXHm2G1xpAE2TmzQ6JCyIRegNxAwo+a10AuIgjigXxTSCT8E2LpHOUW Nf8Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@rasmusvillemoes.dk header.s=google header.b=UDOfn0BF; 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 Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id d2-v6si22143625plh.387.2018.05.07.14.41.41; Mon, 07 May 2018 14:41:55 -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=@rasmusvillemoes.dk header.s=google header.b=UDOfn0BF; 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 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753051AbeEGVlR (ORCPT + 99 others); Mon, 7 May 2018 17:41:17 -0400 Received: from mail-wm0-f49.google.com ([74.125.82.49]:53789 "EHLO mail-wm0-f49.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752721AbeEGVlQ (ORCPT ); Mon, 7 May 2018 17:41:16 -0400 Received: by mail-wm0-f49.google.com with SMTP id a67so15575827wmf.3 for ; Mon, 07 May 2018 14:41:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rasmusvillemoes.dk; s=google; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=F0oLgBS4P7DLBDMcIH0OIfsGB5c7ApmDBVO/j7xM6l0=; b=UDOfn0BF+/JHjRr1DtawsrJmQLiO7bDC9Ak+HQQGOqujdAkreSXzM07Z+lZ7ktsX4N dXr35B95k0LGWGGsevMhleJYhhMEmaHikBBgc/7SR7H3FD4vP0IpeKg4G3di4uEBHStt mx6chQsIXtfzc934rbhCDVZ4jWmOwZtOu0X8s= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=F0oLgBS4P7DLBDMcIH0OIfsGB5c7ApmDBVO/j7xM6l0=; b=c3IY0zEJ/kDSQMG36ukFGpkgmaJmzQtTIRIfNacuOCG2V6HJ+N8alyJxLfFxzIMGe2 Xr09hQiM/rSeINSW2MYnfgnieCsSgSpe5BQV0JgILco8O8xgxtQzkd6szOtL5FowyxYL Mqla7Wf1jcKj7BJ7s79SKS+nVkhxr1XqikgND+3hGIh8iefjnefb0fvbtJf0gO9tq0h3 SUjJW4Aq6aiB/xgE8k/WR9sqnZeRJYOA09sZLN0jYI6RVC5YRRuNRi40Yt6sK0kHQ4jp O3Cqbt6uVXMyHWAXwoDrE8y6nvfEHnZvP6+HQJr9JvuYmrrVcJY6hZTi2JinD0YiQSkX TnqQ== X-Gm-Message-State: ALQs6tD8UeluWyEZCgK6Wa6+aCpojs+n8T8HTarS82gfTEyfIkg0merb ahgS1iaWW5z6Kmhu6RqaEZ+GJntG4hg= X-Received: by 2002:a50:a926:: with SMTP id l35-v6mr39141750edc.106.1525729274505; Mon, 07 May 2018 14:41:14 -0700 (PDT) Received: from [192.168.0.189] (dhcp-5-186-126-104.cgn.ip.fibianet.dk. [5.186.126.104]) by smtp.gmail.com with ESMTPSA id o47-v6sm13608712edc.95.2018.05.07.14.41.13 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 07 May 2018 14:41:14 -0700 (PDT) Subject: Re: *alloc API changes To: Kees Cook , Matthew Wilcox Cc: Matthew Wilcox , Linux-MM , LKML References: <20180505034646.GA20495@bombadil.infradead.org> From: Rasmus Villemoes Message-ID: Date: Mon, 7 May 2018 23:41:13 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 2018-05-05 06:24, Kees Cook wrote: > >> Right, I was thinking: >> >> static inline size_t mul_ab(size_t a, size_t b) >> { >> #if COMPILER_SUPPORTS_OVERFLOW >> unsigned long c; >> if (__builtin_mul_overflow(a, b, &c)) >> return SIZE_MAX; >> return c; >> #else >> if (b != 0 && a >= SIZE_MAX / b) >> return SIZE_MAX; >> return a * b; >> #endif >> } > > Rasmus, what do you think of a saturating version of your helpers? They'd be trivial to implement (using the __type_max that I had to introduce anyway), and I'd prefer they'd have sat_ in their name - not just smult, s would more likely be interpreted as "signed". On that note, I'd want to enforce the sat_ ones are only used for unsigned types, because there's no sane value to saturate to for signed operands. But I don't think we should do the allocation-overflow in terms of saturate-and-rely-on-allocator-rejecting it. I suppose we'll still have the computation done in a static inline (to let the compiler see if one or both operands are constants, and generate code accordingly). If we do static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags) { size_t p; p = sat_mul(n, size); return __kmalloc(p, flags); } with sat_mul being implemented in terms of __builtin_mul_overflow(), gcc will probably waste a temp register on loading SIZE_MAX (or whatever sentinel we use), and do a pipeline-stalling cmov to the register used to pass p. If instead we do static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags) { size_t p; if (check_mul_overflow(n, size, &p)) return NULL; return __kmalloc(p, flags); } we'd not get any extra code in the caller (that is, just a "mul" and "jo", instead of a load-immediate, mul, cmov), because gcc should be smart enough to combine the "return NULL" with the test for NULL which the caller code has, and thus make the jump go directly to the error handling (that error handling is likely itself a jump, but the "jo" will just get redirected to the target of that one). Also, I'd hate to have sat_mul not really saturating to type_max(t), but some large-enough-that-all-underlying-allocators-reject-it. > 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. > >> You don't need the size check here. We have the size check buried deep in >> alloc_pages (look for MAX_ORDER), so kmalloc and then alloc_pages will try >> a bunch of paths all of which fail before returning NULL. > > Good point. Though it does kind of creep me out to let a known-bad > size float around in the allocator until it decides to reject it. I > would think an early: > > if (unlikely(size == SIZE_MAX)) > return NULL; > > would have virtually no cycle count difference... All allocators still need to reject insane sizes, since those can happen without coming from a multiplication. So sure, some early size > MAX_SANE_SIZE check in the out-of-line functions should be rather cheap, and they most likely already exist in some form. But we don't _have_ to go out of our way to make the multiplication overflow handling depend on those. > > 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); Urgh. Do you want to get completely rid of kmalloc_array() and move the mul() into the call-sites? That obviously necessitates mul returning a big-enough sentinel. I'd hate that. Not just because of the code-gen, but also because of the problem with giving mul() sane semantics that still make it immune to the extra arithmetic that will inevitably be done. There's also the problem with foo and bar having different, possibly signed, types - how should mul() handle those? A nice benefit from having the static inline wrappers taking size_t is that a negative value gets converted to a huge positive value, and then the whole thing overflows. Sure, you can build that into mul() (maybe make that itself a static inline), but then it doesn't really deserve that generic name anymore. > and > > kmalloc(foo * bar, GFP_KERNEL | __GFP_ZERO); > into > kzalloc(foo * bar, GFP_KERNEL); > into > kcalloc(foo, bar, GFP_KERNEL); > into > kzalloc(mul(foo, bar), GFP_KERNEL); Yeah, part of the API mess is just copied from C (malloc vs calloc). We could make it a bit less messy by calling it kzalloc_array, but we have 1700 callers of kcalloc(), so... Rasmus