From patchwork Fri Feb 9 14:39:11 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andre Przywara X-Patchwork-Id: 127841 Delivered-To: patch@linaro.org Received: by 10.46.124.24 with SMTP id x24csp679839ljc; Fri, 9 Feb 2018 06:42:12 -0800 (PST) X-Google-Smtp-Source: AH8x226BtNOqZW8CVxRtrjLibDus8q4ic9SZcTQFIgjeFTuPrSc57qbKBgeysYTCMdPkrr5MsyNh X-Received: by 10.36.124.84 with SMTP id a81mr3418858itd.97.1518187332785; Fri, 09 Feb 2018 06:42:12 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1518187332; cv=none; d=google.com; s=arc-20160816; b=vHV3elKyZs0KX3MmQnFqCcutzMQoGfLnKZG24PFQLfh8h+UVes+JryqK+0CYL8uLun oAMVkPSS7Ioa5aIpin7VChws3ZxaiLFRx5nUzWgy6fVwW22Jnb3bG2R4buBRaJXfhCjC P4rNPMiFkHDmefFDNN5DeTg8CMpWRqNXavcwh8y+voGhe/Kl5UazOSKJxVoZAcVxxcGi Z1LwBFUQGgUpi38LKeIROCYNxVAekNadQnuFL2O73dWgWiYKNMZJRbzbikokuGqIePk7 6yE/yFvXSz80UadXq9qyWHOV6q1LtK2zv7sqJ0qFWoxQ6Bvl0g8NwbFdBcbpw1g/AzM+ CmqQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:mime-version :list-subscribe:list-help:list-post:list-unsubscribe:list-id :precedence:subject:references:in-reply-to:message-id:date:to:from :dkim-signature:arc-authentication-results; bh=DHtZJcIeUfwQkCgGoWcE/qdlIsgn2Oegs2IeayW/Nyc=; b=X9wetN/VTFtMnj/vQP57ysWoRcCqEcH2XjEh641OElfzARG6wvplPfs9vp/F6dlRgk hJ7MJhbwz8Z+4mGXxVH15Dmbtnyv4BvPpsP4fZkdKFx3Vxw7d0ZJwGkAk6a2rhPa1wX1 V1ocauArmJSohjN7vjEPZuuUETUK6bu4zjNkBE1q6S19vhxjAfwzhoHjOHIRLPf2Ijxy qRY+gI75yuimWVR6/asAyPuPQHBcofjSmUUTnsK8xeIMNS4lexX10x478gF8f7F2NmRT uCeBLefYzyS/f0YcbAcOiYY9LqtZH/uIap06KhDeL4Z/sLDOu66RtmsnYRkGzrDqJRkB xKeA== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@linaro.org header.s=google header.b=CT905u/i; spf=pass (google.com: best guess record for domain of xen-devel-bounces@lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.xenproject.org (lists.xenproject.org. [192.237.175.120]) by mx.google.com with ESMTPS id u68si139296itb.14.2018.02.09.06.42.12 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 09 Feb 2018 06:42:12 -0800 (PST) Received-SPF: pass (google.com: best guess record for domain of xen-devel-bounces@lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@linaro.org header.s=google header.b=CT905u/i; spf=pass (google.com: best guess record for domain of xen-devel-bounces@lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ek9qW-0000kD-Uf; Fri, 09 Feb 2018 14:40:12 +0000 Received: from us1-rack-dfw2.inumbo.com ([104.130.134.6]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ek9qV-0000gx-Um for xen-devel@lists.xenproject.org; Fri, 09 Feb 2018 14:40:11 +0000 X-Inumbo-ID: 103d3198-0da7-11e8-ba59-bc764e045a96 Received: from mail-wm0-x243.google.com (unknown [2a00:1450:400c:c09::243]) by us1-rack-dfw2.inumbo.com (Halon) with ESMTPS id 103d3198-0da7-11e8-ba59-bc764e045a96; Fri, 09 Feb 2018 15:39:42 +0100 (CET) Received: by mail-wm0-x243.google.com with SMTP id i186so15772903wmi.4 for ; Fri, 09 Feb 2018 06:40:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=ZV0vm2gT3QLBAEPaIpCUwXdZ7pY/v9GnyQ8CNtUzA5U=; b=CT905u/i9HlR2N+lvhGI9Lvy4aHHqnchgicpUZZBbtdQE1D0whmJ3dpBLCX1HOK1xO 1Vh+KsN4MiMpV1Ff/3EFrcSQl7IRk8m7MGkcoKX5F3T/JB0rDoKT4jB5p3EG4xxJiJla 6lBjLJ6CgqWzaCDBNXZlBTMirVmi9Gc6AE8ZE= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=ZV0vm2gT3QLBAEPaIpCUwXdZ7pY/v9GnyQ8CNtUzA5U=; b=SQgc1knMCNH9+v+mwzkkPdPE3UGgODpnAVqx8jdX/W9SjsTYi766DF24tm/NEFh0Jg jd6tPxf89vkQRDy+aqJvSdftgzICbDh0QIHXnWL50sfalkymGVKKWzHaH+lP3NADsRNh tvvkEdablwDjACg9X+xyZ7aHVemZO5cj7EesF/aEajsNfdAG31MpYIggUJLs36kXQGkj B9TDBHWXXg6dCOeLbJ1di2i01/tXLqUBRQHjhA1sAgoVvpVl0eD7Bzpz6A30qGUl7UTK By2wNRaO8h/hrJ2J3T8loxEmAt6TYLzrPJ+cmnRVIIDXTawTCuEg6tXf8jerMDh9wMNk 8/Pg== X-Gm-Message-State: APf1xPB8T8CJZP4WqNkXGHkacz/8VyCidDX8i2Ty7ZFz4qCzCrQrS0r9 JaIqh+auA/rfFWqvwsqgI91kgGiz4NI= X-Received: by 10.28.23.14 with SMTP id 14mr2354658wmx.5.1518187209374; Fri, 09 Feb 2018 06:40:09 -0800 (PST) Received: from e104803-lin.lan (mail.andrep.de. [217.160.17.100]) by smtp.gmail.com with ESMTPSA id b35sm2552229wra.13.2018.02.09.06.40.08 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 09 Feb 2018 06:40:08 -0800 (PST) From: Andre Przywara To: Stefano Stabellini , Julien Grall , xen-devel@lists.xenproject.org Date: Fri, 9 Feb 2018 14:39:11 +0000 Message-Id: <20180209143937.28866-24-andre.przywara@linaro.org> X-Mailer: git-send-email 2.14.1 In-Reply-To: <20180209143937.28866-1-andre.przywara@linaro.org> References: <20180209143937.28866-1-andre.przywara@linaro.org> Subject: [Xen-devel] [RFC PATCH 23/49] ARM: new VGIC: Add IRQ sorting X-BeenThere: xen-devel@lists.xenproject.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: xen-devel-bounces@lists.xenproject.org Sender: "Xen-devel" Adds the sorting function to cover the case where you have more IRQs to consider than you have LRs. We consider their priorities. This pulls in Linux' list_sort.c , which is a merge sort implementation for linked lists. This is based on Linux commit 8e4447457965, written by Christoffer Dall. Signed-off-by: Andre Przywara --- xen/arch/arm/vgic/vgic.c | 59 +++++++++++++++ xen/common/list_sort.c | 170 ++++++++++++++++++++++++++++++++++++++++++++ xen/include/xen/list_sort.h | 11 +++ 3 files changed, 240 insertions(+) create mode 100644 xen/common/list_sort.c create mode 100644 xen/include/xen/list_sort.h diff --git a/xen/arch/arm/vgic/vgic.c b/xen/arch/arm/vgic/vgic.c index f517df6d00..a4efd1fd03 100644 --- a/xen/arch/arm/vgic/vgic.c +++ b/xen/arch/arm/vgic/vgic.c @@ -16,6 +16,7 @@ */ #include +#include #include #include @@ -163,6 +164,64 @@ static struct vcpu *vgic_target_oracle(struct vgic_irq *irq) return NULL; } +/* + * The order of items in the ap_lists defines how we'll pack things in LRs as + * well, the first items in the list being the first things populated in the + * LRs. + * + * A hard rule is that active interrupts can never be pushed out of the LRs + * (and therefore take priority) since we cannot reliably trap on deactivation + * of IRQs and therefore they have to be present in the LRs. + * + * Otherwise things should be sorted by the priority field and the GIC + * hardware support will take care of preemption of priority groups etc. + * + * Return negative if "a" sorts before "b", 0 to preserve order, and positive + * to sort "b" before "a". + */ +static int vgic_irq_cmp(void *priv, struct list_head *a, struct list_head *b) +{ + struct vgic_irq *irqa = container_of(a, struct vgic_irq, ap_list); + struct vgic_irq *irqb = container_of(b, struct vgic_irq, ap_list); + bool penda, pendb; + int ret; + + spin_lock(&irqa->irq_lock); + spin_lock(&irqb->irq_lock); + + if ( irqa->active || irqb->active ) + { + ret = (int)irqb->active - (int)irqa->active; + goto out; + } + + penda = irqa->enabled && irq_is_pending(irqa); + pendb = irqb->enabled && irq_is_pending(irqb); + + if ( !penda || !pendb ) + { + ret = (int)pendb - (int)penda; + goto out; + } + + /* Both pending and enabled, sort by priority */ + ret = irqa->priority - irqb->priority; +out: + spin_unlock(&irqb->irq_lock); + spin_unlock(&irqa->irq_lock); + return ret; +} + +/* Must be called with the ap_list_lock held */ +static void vgic_sort_ap_list(struct vcpu *vcpu) +{ + struct vgic_cpu *vgic_cpu = &vcpu->arch.vgic_cpu; + + ASSERT(spin_is_locked(&vgic_cpu->ap_list_lock)); + + list_sort(NULL, &vgic_cpu->ap_list_head, vgic_irq_cmp); +} + /* * Only valid injection if changing level for level-triggered IRQs or for a * rising edge. diff --git a/xen/common/list_sort.c b/xen/common/list_sort.c new file mode 100644 index 0000000000..9c5cc58e43 --- /dev/null +++ b/xen/common/list_sort.c @@ -0,0 +1,170 @@ +/* + * list_sort.c: merge sort implementation for linked lists + * Copied from the Linux kernel (lib/list_sort.c) + * (without specific copyright notice there) + * + * This program is free software; you can redistribute it and/or modify it + * under the terms and conditions of the GNU General Public License, + * version 2, as published by the Free Software Foundation. + * + * This program is distributed in the hope it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; If not, see . + */ +#include +#include + +#define MAX_LIST_LENGTH_BITS 20 + +/* + * Returns a list organized in an intermediate format suited + * to chaining of merge() calls: null-terminated, no reserved or + * sentinel head node, "prev" links not maintained. + */ +static struct list_head *merge(void *priv, + int (*cmp)(void *priv, struct list_head *a, + struct list_head *b), + struct list_head *a, struct list_head *b) +{ + struct list_head head, *tail = &head; + + while ( a && b ) + { + /* if equal, take 'a' -- important for sort stability */ + if ( (*cmp)(priv, a, b) <= 0 ) + { + tail->next = a; + a = a->next; + } + else + { + tail->next = b; + b = b->next; + } + tail = tail->next; + } + tail->next = a?:b; + return head.next; +} + +/* + * Combine final list merge with restoration of standard doubly-linked + * list structure. This approach duplicates code from merge(), but + * runs faster than the tidier alternatives of either a separate final + * prev-link restoration pass, or maintaining the prev links + * throughout. + */ +static void merge_and_restore_back_links(void *priv, + int (*cmp)(void *priv, + struct list_head *a, + struct list_head *b), + struct list_head *head, + struct list_head *a, + struct list_head *b) +{ + struct list_head *tail = head; + u8 count = 0; + + while ( a && b ) + { + /* if equal, take 'a' -- important for sort stability */ + if ( (*cmp)(priv, a, b) <= 0 ) + { + tail->next = a; + a->prev = tail; + a = a->next; + } + else + { + tail->next = b; + b->prev = tail; + b = b->next; + } + tail = tail->next; + } + tail->next = a ? : b; + + do + { + /* + * In worst cases this loop may run many iterations. + * Continue callbacks to the client even though no + * element comparison is needed, so the client's cmp() + * routine can invoke cond_resched() periodically. + */ + if ( unlikely(!(++count)) ) + (*cmp)(priv, tail->next, tail->next); + + tail->next->prev = tail; + tail = tail->next; + } while ( tail->next ); + + tail->next = head; + head->prev = tail; +} + +/** + * list_sort - sort a list + * @priv: private data, opaque to list_sort(), passed to @cmp + * @head: the list to sort + * @cmp: the elements comparison function + * + * This function implements "merge sort", which has O(nlog(n)) + * complexity. + * + * The comparison function @cmp must return a negative value if @a + * should sort before @b, and a positive value if @a should sort after + * @b. If @a and @b are equivalent, and their original relative + * ordering is to be preserved, @cmp must return 0. + */ +void list_sort(void *priv, struct list_head *head, + int (*cmp)(void *priv, struct list_head *a, struct list_head *b)) +{ + struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists + -- last slot is a sentinel */ + int lev; /* index into part[] */ + int max_lev = 0; + struct list_head *list; + + if ( list_empty(head) ) + return; + + memset(part, 0, sizeof(part)); + + head->prev->next = NULL; + list = head->next; + + while ( list ) + { + struct list_head *cur = list; + list = list->next; + cur->next = NULL; + + for ( lev = 0; part[lev]; lev++ ) + { + cur = merge(priv, cmp, part[lev], cur); + part[lev] = NULL; + } + if ( lev > max_lev ) + { + if ( unlikely(lev >= ARRAY_SIZE(part)-1) ) + { + dprintk(XENLOG_DEBUG, "list too long for efficiency\n"); + lev--; + } + max_lev = lev; + } + part[lev] = cur; + } + + for ( lev = 0; lev < max_lev; lev++ ) + if ( part[lev] ) + list = merge(priv, cmp, part[lev], list); + + merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); +} +EXPORT_SYMBOL(list_sort); diff --git a/xen/include/xen/list_sort.h b/xen/include/xen/list_sort.h new file mode 100644 index 0000000000..a60c589d4b --- /dev/null +++ b/xen/include/xen/list_sort.h @@ -0,0 +1,11 @@ +#ifndef _LINUX_LIST_SORT_H +#define _LINUX_LIST_SORT_H + +#include + +struct list_head; + +void list_sort(void *priv, struct list_head *head, + int (*cmp)(void *priv, struct list_head *a, + struct list_head *b)); +#endif