Received: by 2002:a25:8b91:0:0:0:0:0 with SMTP id j17csp2360882ybl; Sat, 11 Jan 2020 15:23:44 -0800 (PST) X-Google-Smtp-Source: APXvYqyPxBJrq6sgVX1D/lDdjZPnwNSjstCw0hpVfWKYLOtzsKzqSOdpxdyZ/FnZPnLDG8WYuA9H X-Received: by 2002:a05:6830:18fa:: with SMTP id d26mr3113069otf.305.1578785024538; Sat, 11 Jan 2020 15:23:44 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1578785024; cv=none; d=google.com; s=arc-20160816; b=KzKV0rF7cjiFu0KaOCgz8MO16YphmPJ/6/ioeBvAC6RY/OQ8+z8+wuPAoa4m0QOgZ3 CNmjN3cG7/kMzbbsdjwoDSSaNXa8cW6WOD6qMxR3oW3lruSmonXDomPBC6mC+JOldGZi l2tJSWkl4UDOjw7CZdAaTqDki4qIi2KZFtjR2lhyQBG2X846Q+sSA2Ah2x0CxpRMgmQ6 FUNCZVHh27ldpDbo6dM0Zf5GcGtyN3B7dRE5vRCPeISzXruwfsC4Omp6uOWN1AMaPKqn NwJWzByWehLDoeDPgnHsbItddbQRPQ/zZK7NjlTcCMdshXOORXY3BqVRnCdroJnSU7ZY V9FA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:cc:subject:to :message-id:from:date; bh=6wxF13e75psAxXAEi3BQpgCK274U887VABQE4yfIBto=; b=S+DTmUPc8is0S5cqnb0hqa/3oIMtCBsP68DadD4n91i5jt9aVovah2Q+jllmwI9OXS cZO6xdkompQA+xOYkV/42pfinE4L5ZRtxsziYPuf59n2TmzjjjTLzPr8XRyu1Y3fF/Wq DA4ykR/UuTEK5RkQ+H26l45+uMyLOVYUTSP+pIPQ+0cqHiVvXMhS5qxEGKEFAO7iDiCW MepxM5VeGpfk32vKlMQQvCG0LwSwE3jCArjlKkoAskdB7jRTuIkca+2TxNAuEQNPWERi WNTSoBZzZq48O3FFI8upC6TPJ9qoYyimHm5wEcRLEC4c/vKqM4f0BrEbO8/SUy/ZuUbv oKCg== ARC-Authentication-Results: i=1; mx.google.com; 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 g138si3992159oib.190.2020.01.11.15.23.32; Sat, 11 Jan 2020 15:23:44 -0800 (PST) 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; 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 S1731656AbgAKXWf (ORCPT + 99 others); Sat, 11 Jan 2020 18:22:35 -0500 Received: from mx.sdf.org ([205.166.94.20]:49296 "EHLO mx.sdf.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730708AbgAKXWf (ORCPT ); Sat, 11 Jan 2020 18:22:35 -0500 Received: from sdf.org (IDENT:lkml@sdf.lonestar.org [205.166.94.16]) by mx.sdf.org (8.15.2/8.14.5) with ESMTPS id 00BNMN9l022260 (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256 bits) verified NO); Sat, 11 Jan 2020 23:22:24 GMT Received: (from lkml@localhost) by sdf.org (8.15.2/8.12.8/Submit) id 00BNMp7Q002616; Sat, 11 Jan 2020 23:22:51 GMT Date: Sat, 11 Jan 2020 23:22:51 GMT From: George Spelvin Message-Id: <202001112322.00BNMp7Q002616@sdf.org> To: andy.shevchenko@gmail.com, kbusch@kernel.org, lkml@sdf.org Subject: Re: [PATCH] lib/list_sort: fix function type mismatches Cc: akpm@linux-foundation.org, andriy.shevchenko@linux.intel.com, keescook@chromium.org, linux-kernel@vger.kernel.org, linux@rasmusvillemoes.dk, mchehab+samsung@kernel.org, samitolvanen@google.com, st5pub@yandex.ru In-Reply-To: <202001111144.00BBiXEq002960@sdf.org> References: <20200110225602.91663-1-samitolvanen@google.com>, <202001110830.00B8USV0024843@sdf.org>, , <202001111144.00BBiXEq002960@sdf.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org (Resend with corrected e-mail address and more thoughts.) On Sat, 11 Jan 2020 at 12:35, Andy Shevchenko wrote: > Hint: When you post Message-Id you may prefix them with > https://lore.kernel.org/r/ which makes search a bit more convenient > and faster. I just learned that https://marc.info/?i= also works, so https://lore.kernel.org/r/20191007135656.37734-1-andriy.shevchenko@linux.intel.com https://marc.info/?i=20191007135656.37734-1-andriy.shevchenko@linux.intel.com https://lore.kernel.org/r/20190416154522.65aaa348161fc581181b56d9@linux-foundation.org https://marc.info/?i=20190416154522.65aaa348161fc581181b56d9@linux-foundation.org > For the record, I have just checked users of list_sort() in regard to > constify of priv parameter and only ACPI HMAT is using it as not > const. UBIFS and XFS do not change the data (if I didn't miss > anything). Yes, that initiator_cmp() at drivers/acpi/hmat/hmat.c:526 is... interesting. Basically, it wants to fill in a bitmap of all of the processor_pxm identifiers, so it avoids having a separate list traversal by setting bits in the compare function (which is guaranteed to visit each list element at least once). It ends up setting each bit 2*log2(n) times (since there are an average of log2(n) compares per element and each compare sets two bits), but it makes the code smaller. And although it make the aggressive performance optimizer in me cringe, I have to agree this is not performance-critical code and so it's a reasonable thing to do. I do note, however, that the list_sort is almost immediately followed by a list_for_each_entry() loop and maybe the bitmap computation could be folded in there. Basically start the loop with: unsigned int pxm = -1u; /* Invalid sentinel value */ list_for_each_entry(initiator, &initiators, node) { u32 value; if (initiator->processor_pxm != pxm) { pxm = initiator->processor_pxm; set_bit(pxm, p_nodes); } else if (!test_bit(pxm, p_nodes)) { continue; } ... but oh, whoops, that won't work. The "almost immediately" glosses over a second loop, so there are multiple passes over the initiators list, while we want the bitmap set up only once. What we should probably do is just cast away the const in the cmp function. That's a strange thing to do, which is appropriate because the code is doing something strange. It might be too subtle, but given the semantics guaranteed by list_sort, it would suffice to set only the bit corresponding to the *second* argument to cmp(), plus the bit corresponding to the first element of the input (not yet sorted) list. Cc: to Keith Busch , who wrote that code. Keith, is there a better way we could avoid the non-const priv parameter, just for the sake of code cleanliness in ?