Received: by 2002:a25:1506:0:0:0:0:0 with SMTP id 6csp344243ybv; Wed, 5 Feb 2020 06:34:53 -0800 (PST) X-Google-Smtp-Source: APXvYqzRQ0teTipOEMkUaXYLRxgnbg3UQEgNKYiGFrygCoVZ3DP1s+oSY9GdSi4iHW+4nd4Z4XeA X-Received: by 2002:a54:488d:: with SMTP id r13mr2906903oic.115.1580913293848; Wed, 05 Feb 2020 06:34:53 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1580913293; cv=none; d=google.com; s=arc-20160816; b=AsTDIEElL9s/mCXTqoTbDnNX9JxeCkSy2pYtxU/MOVKfejNOfe4krXpa9ZtTd+v5is qY31ts760Oi4m4OECag+TWphoxFuFlPenkS44jpmEX0hR+b6oYzocg0TkWOuCQ7+yg05 XoHF5TWsgrhapfF7K/JAgKw05jklbmRnOazIDI50H/bp9SLnAixoFa2QV/3fO7CSjD13 schnFo3LzPMTowxtA49oX6SQ6NWSABNpwU9gpURqA+kuwJb3hRN+2JBXHqgPyAgCXxDO olH7stpcwGKt7BfbN+3k7wAdi+gySJLma93szDKalgt2kQ7iKxvbZ6cPQi+t1HkTKL58 Al/w== 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; bh=a2Q+FJJ7ymzq1vpGgV7nlcxJJEeDcXgTcSuun2ahR3E=; b=pmmO8yj1OFrz0HGsOsNSwj7mD4JLmX5o2jJqoNUaJKuyBfca2hdp9vElT57IfXtZXk /QRuAI0p+TzGYRUnxF/HjlVVul4YME4C/5UdUj6Vj7IMARa/q2fyBzKK8O4DVNO86eT7 cseybrqGR13PYVmFB4JD0rMJN5pIXGofCD6ryEQDZ6R+vlSUHulOTcL60FjSiZ/7FvNT 42ZH7B6NvUzh6hDEKs/GEG+TiDJ4eTklAvTrpt36GCiMEaaRjFhS8xRBTq6uQEp39Jhd dzer7a0KrvPhR9esqPwdYQbYl38BcOSbYuSIDAJ41Obl9UkfpnkTVgqpPxzzlkMbyFQ4 2Blw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=dY3pxJvI; 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=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id t24si4231651oth.319.2020.02.05.06.34.39; Wed, 05 Feb 2020 06:34:53 -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; dkim=pass header.i=@gmail.com header.s=20161025 header.b=dY3pxJvI; 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=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726563AbgBEOdo (ORCPT + 99 others); Wed, 5 Feb 2020 09:33:44 -0500 Received: from mail-ot1-f67.google.com ([209.85.210.67]:42737 "EHLO mail-ot1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726208AbgBEOdo (ORCPT ); Wed, 5 Feb 2020 09:33:44 -0500 Received: by mail-ot1-f67.google.com with SMTP id 66so2065322otd.9 for ; Wed, 05 Feb 2020 06:33:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=a2Q+FJJ7ymzq1vpGgV7nlcxJJEeDcXgTcSuun2ahR3E=; b=dY3pxJvID6PLcV83rCPo28gm7GHN2YwlG9xrPqmyMSuFgvc3NLlLykZMCsM8jGbpLJ 2nUSXqHjCfPticf1Ouuch3siGfCW9d2R1hftHLXQrirh8PW4V1MAGhy+XiV3orr5hy5e STSNinpP5wR3wE3otHFW1enNLMrXOv3jGHFReBD0xq0zRXMw3m6UO8BqgirsvOy8ajfn JzmhY11rg74Z8Fq/PChhoYF/W5WJyfumAyudYtHKtKr0dsBpXueicdoaQlSboii4z7Lv xqJOrooZqbc8kMTVwR8YMKdba8dvf/GialehxZAajunNc1cyG1Nab6FKV0VHy+dZ+MV8 XM7Q== 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=a2Q+FJJ7ymzq1vpGgV7nlcxJJEeDcXgTcSuun2ahR3E=; b=cNDD2CpWXoBbXpjV+HA3FpC5jhSQEf9jJQiF4yEcamgHZS3nQkig07W73YxxOKovjN K6vx280C16qLIvxhYRDCeZNxGAkHQlsCBrg6WGuKpF9ZmHO6CeNzD7G92d3fpdtfP4m1 y6CbVTBMyZ3xBBsq5JgiG5fpnCy6vXlf07iwWgDJJFQUEAMtjbZrClY+lN56UNNPTET4 Q+W2iCxKvSAbszcJBZbLu+w8Nl7tpM7P/YSrgnambvc4boFxNFm/OsO1N6f1YeHHV5FN S2nf7U78YB8zilvuqgLed5j5YSE4pu/+N7ZU7E0ibpYPMry/lTqtRhQIK1L6rAoxHUFT JLjA== X-Gm-Message-State: APjAAAUpXDcfLHlj8LIjz9z441f2wv4ojaC8Z66q2za69lNhs5iBksPr qBh5ZhvBHG5X4O+LfgTPIQ== X-Received: by 2002:a05:6830:155a:: with SMTP id l26mr26380657otp.339.1580913223228; Wed, 05 Feb 2020 06:33:43 -0800 (PST) Received: from [172.31.9.147] (ausvpn.amd.com. [165.204.77.11]) by smtp.gmail.com with ESMTPSA id j45sm8895622ota.59.2020.02.05.06.33.41 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 05 Feb 2020 06:33:42 -0800 (PST) Subject: Re: [PATCH] powerpc/drmem: cache LMBs in xarray to accelerate lookup To: Scott Cheloha , Nathan Lynch Cc: Rick Lindsley , linuxppc-dev@lists.ozlabs.org, linux-kernel@vger.kernel.org, Michael Ellerman References: <20200128221113.17158-1-cheloha@linux.ibm.com> <87pnf3i188.fsf@linux.ibm.com> <20200129181013.lz6q5lpntnhwclqi@rascal.austin.ibm.com> <4dfb2f93-7af8-8c5f-854c-22afead18a8c@gmail.com> <20200203201346.deqkxwgfmkifeb5s@rascal.austin.ibm.com> From: "Fontenot, Nathan" Message-ID: <081c4f0e-5d7a-93c1-2075-608790f8e35f@gmail.com> Date: Wed, 5 Feb 2020 08:33:40 -0600 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.4.2 MIME-Version: 1.0 In-Reply-To: <20200203201346.deqkxwgfmkifeb5s@rascal.austin.ibm.com> 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 2/3/2020 2:13 PM, Scott Cheloha wrote: > On Thu, Jan 30, 2020 at 10:09:32AM -0600, Fontenot, Nathan wrote: >> On 1/29/2020 12:10 PM, Scott Cheloha wrote: >>> On Tue, Jan 28, 2020 at 05:56:55PM -0600, Nathan Lynch wrote: >>>> Scott Cheloha writes: >>>>> LMB lookup is currently an O(n) linear search. This scales poorly when >>>>> there are many LMBs. >>>>> >>>>> If we cache each LMB by both its base address and its DRC index >>>>> in an xarray we can cut lookups to O(log n), greatly accelerating >>>>> drmem initialization and memory hotplug. >>>>> >>>>> This patch introduces two xarrays of of LMBs and fills them during >>>>> drmem initialization. The patch also adds two interfaces for LMB >>>>> lookup. >>>> >>>> Good but can you replace the array of LMBs altogether >>>> (drmem_info->lmbs)? xarray allows iteration over the members if needed. >>> >>> I don't think we can without potentially changing the current behavior. >>> >>> The current behavior in dlpar_memory_{add,remove}_by_ic() is to advance >>> linearly through the array from the LMB with the matching DRC index. >>> >>> Iteration through the xarray via xa_for_each_start() will return LMBs >>> indexed with monotonically increasing DRC indices.> >>> Are they equivalent? Or can we have an LMB with a smaller DRC index >>> appear at a greater offset in the array? >>> >>> If the following condition is possible: >>> >>> drmem_info->lmbs[i].drc_index > drmem_info->lmbs[j].drc_index >>> >>> where i < j, then we have a possible behavior change because >>> xa_for_each_start() may not return a contiguous array slice. It might >>> "leap backwards" in the array. Or it might skip over a chunk of LMBs. >>> >> >> The LMB array should have each LMB in monotonically increasing DRC Index >> value. Note that this is set up based on the DT property but I don't recall >> ever seeing the DT specify LMBs out of order or not being contiguous. > > Is that ordering guaranteed by the PAPR or some other spec or is that > just a convention? From what I remember the PAPR does not specify that DRC indexes are guaranteed to be contiguous. In past discussions with pHyp developers I had been told that they always generate contiguous DRC index values but without a specification in the PAPR that could always break. -Nathan > > Code like drmem_update_dt_v1() makes me very nervous: > > static int drmem_update_dt_v1(struct device_node *memory, > struct property *prop) > { > struct property *new_prop; > struct of_drconf_cell_v1 *dr_cell; > struct drmem_lmb *lmb; > u32 *p; > > new_prop = clone_property(prop, prop->length); > if (!new_prop) > return -1; > > p = new_prop->value; > *p++ = cpu_to_be32(drmem_info->n_lmbs); > > dr_cell = (struct of_drconf_cell_v1 *)p; > > for_each_drmem_lmb(lmb) { > dr_cell->base_addr = cpu_to_be64(lmb->base_addr); > dr_cell->drc_index = cpu_to_be32(lmb->drc_index); > dr_cell->aa_index = cpu_to_be32(lmb->aa_index); > dr_cell->flags = cpu_to_be32(drmem_lmb_flags(lmb)); > > dr_cell++; > } > > of_update_property(memory, new_prop); > return 0; > } > > If for whatever reason the firmware has a DRC that isn't monotonically > increasing and we update a firmware property at the wrong offset I have > no idea what would happen. > > With the array we preserve the order. Without it we might violate > some assumption the firmware has made. >