From patchwork Thu Jan 18 18:04:56 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jens Axboe X-Patchwork-Id: 13523085 Received: from mail-il1-f182.google.com (mail-il1-f182.google.com [209.85.166.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D447A2D608 for ; Thu, 18 Jan 2024 18:05:50 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705601154; cv=none; b=Swm6wdYIimPIPtsqPUnD7jgmL37znsOk9sr8b6wwZUFt8WnJj/V4S+lIZqdr3+R8LsTkmoLbvEkg+mCMtjwfbHuQWufF5K5gBJhs7umAIaWMZJJ73f/NSjKs+8yL55NFBWloYyyXy81HZiyWttWHGGabSHAxUdjU3CS4NwilJww= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705601154; c=relaxed/simple; bh=Op4Kp8hTPdJBcXksFX1xaIIuSLH/ueMSx0RyUzuZIe0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=uzfgHaa4Cc6s5LhIjYa2eNk5FageOOAw11G8JF9GoIfBzJSmwzpbHPoSNewgZdtYg9KyQANZSuLSmCKoSvYgW02aXSdK0OPWnCd0uavYAFkkI70P0vxIbXrb62CtY0cNiPNj/GiDbKoba1PFFIDu6bG+8apz9b45CxsM6n6wuJc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=kernel.dk; spf=pass smtp.mailfrom=kernel.dk; dkim=pass (2048-bit key) header.d=kernel-dk.20230601.gappssmtp.com header.i=@kernel-dk.20230601.gappssmtp.com header.b=VgzEdnCZ; arc=none smtp.client-ip=209.85.166.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=kernel.dk Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=kernel.dk Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel-dk.20230601.gappssmtp.com header.i=@kernel-dk.20230601.gappssmtp.com header.b="VgzEdnCZ" Received: by mail-il1-f182.google.com with SMTP id e9e14a558f8ab-35d374bebe3so9915495ab.1 for ; Thu, 18 Jan 2024 10:05:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel-dk.20230601.gappssmtp.com; s=20230601; t=1705601149; x=1706205949; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=P5Yv2/ThtSVPIwMNI0HbpzQ4mlcRZBuPxJLVsJs0fIk=; b=VgzEdnCZBt0nU04BEdIrsRq4HPljO+6zEGaa+UgqUv+tGO8sSqQeLVKwg6+/NfGgBZ ZE7FSRl//d4ZGPkU8PmnfbLd6InlIRoeiYf6CcsIO0cP8LYq1sNmlhJn2WRCZZqR0mss GDz2uo+BYIU0IAvW6f1dv0ckz20ZuSlOX8YEhq3V7Et5Q8GQEN3DeCcLALS+UYTcJf6S X4XVj1eaYEivjD+7sYm2dba8JviiFUs034WmeVLX1lNMINweThMn02GTbzenQxpiSLaS ewnPwCy1Jlm5iiCNQuzriuBACVgxBsvW4yZlVi1eK7yIm+4Wdl9xKzttupfAwYUDAuHD mJ3A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705601149; x=1706205949; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=P5Yv2/ThtSVPIwMNI0HbpzQ4mlcRZBuPxJLVsJs0fIk=; b=cQPMxsNBjwkIqM+gGOjsfDEOTzfsQDyNQqeBwoF3HfXfYpt3DmtGSQELciK3iO5Mn6 jxHh9ise5REqmTTbiequW9wmev8m69lTH2Ag3Fxr/CnAzQobBq3NX+H6yJAEXV3jNp0L ULCjWoaJqoJDYCgQhJpLGnlb0M8Wq6ADiFM6GWLjyGPaIQHVVAdOspp6IbYF/yIFBfhG rZff05EJYUITbU4zlL90Z5l1FrilS34juM6C8xUxrj0/ENx5DkStm0oDKG9sgmikQM/A 2f+wYxtVmYYPo7VYLvZmUpYreizUzx8wTuRxtxeK/Q7cUUxEQGApT5VwBNO9X3Q468AG Ic4Q== X-Gm-Message-State: AOJu0Yy0iQildG8adT6ztAqn5YHjwx+IMZtum/iWCrzuB291hTksbnNv nkLITyau/Xum8RPzf82t7yA6cYFV9CLR2NlMFvt7VdR5K7rb5M8B+RdHA5dqWZtaGGDKpYiyMKJ TwOE= X-Google-Smtp-Source: AGHT+IE+Lu/oGlAArWM+8UhOoIKimkOYeSdP/QidRGPdNBAwMkioVQcaFIqAX2mGii5S3TDtSYs23w== X-Received: by 2002:a05:6e02:152d:b0:361:9667:9390 with SMTP id i13-20020a056e02152d00b0036196679390mr57313ilu.1.1705601149374; Thu, 18 Jan 2024 10:05:49 -0800 (PST) Received: from localhost.localdomain ([96.43.243.2]) by smtp.gmail.com with ESMTPSA id bq7-20020a056e02238700b0036088147a06sm4981873ilb.1.2024.01.18.10.05.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 18 Jan 2024 10:05:48 -0800 (PST) From: Jens Axboe To: linux-block@vger.kernel.org Cc: bvanassche@acm.org, Jens Axboe Subject: [PATCH 1/2] block/mq-deadline: serialize request dispatching Date: Thu, 18 Jan 2024 11:04:56 -0700 Message-ID: <20240118180541.930783-2-axboe@kernel.dk> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240118180541.930783-1-axboe@kernel.dk> References: <20240118180541.930783-1-axboe@kernel.dk> Precedence: bulk X-Mailing-List: linux-block@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 If we're entering request dispatch but someone else is already dispatching, then just skip this dispatch. We know IO is inflight and this will trigger another dispatch event for any completion. This will potentially cause slightly lower queue depth for contended cases, but those are slowed down anyway and this should not cause an issue. Signed-off-by: Jens Axboe --- block/mq-deadline.c | 28 +++++++++++++++++++++++----- 1 file changed, 23 insertions(+), 5 deletions(-) diff --git a/block/mq-deadline.c b/block/mq-deadline.c index f958e79277b8..9e0ab3ea728a 100644 --- a/block/mq-deadline.c +++ b/block/mq-deadline.c @@ -79,10 +79,20 @@ struct dd_per_prio { struct io_stats_per_prio stats; }; +enum { + DD_DISPATCHING = 0, +}; + struct deadline_data { /* * run time data */ + struct { + spinlock_t lock; + spinlock_t zone_lock; + } ____cacheline_aligned_in_smp; + + unsigned long run_state; struct dd_per_prio per_prio[DD_PRIO_COUNT]; @@ -100,9 +110,6 @@ struct deadline_data { int front_merges; u32 async_depth; int prio_aging_expire; - - spinlock_t lock; - spinlock_t zone_lock; }; /* Maps an I/O priority class to a deadline scheduler priority. */ @@ -600,6 +607,15 @@ static struct request *dd_dispatch_request(struct blk_mq_hw_ctx *hctx) struct request *rq; enum dd_prio prio; + /* + * If someone else is already dispatching, skip this one. This will + * defer the next dispatch event to when something completes, and could + * potentially lower the queue depth for contended cases. + */ + if (test_bit(DD_DISPATCHING, &dd->run_state) || + test_and_set_bit(DD_DISPATCHING, &dd->run_state)) + return NULL; + spin_lock(&dd->lock); rq = dd_dispatch_prio_aged_requests(dd, now); if (rq) @@ -616,6 +632,7 @@ static struct request *dd_dispatch_request(struct blk_mq_hw_ctx *hctx) } unlock: + clear_bit(DD_DISPATCHING, &dd->run_state); spin_unlock(&dd->lock); return rq; @@ -706,6 +723,9 @@ static int dd_init_sched(struct request_queue *q, struct elevator_type *e) eq->elevator_data = dd; + spin_lock_init(&dd->lock); + spin_lock_init(&dd->zone_lock); + for (prio = 0; prio <= DD_PRIO_MAX; prio++) { struct dd_per_prio *per_prio = &dd->per_prio[prio]; @@ -722,8 +742,6 @@ static int dd_init_sched(struct request_queue *q, struct elevator_type *e) dd->last_dir = DD_WRITE; dd->fifo_batch = fifo_batch; dd->prio_aging_expire = prio_aging_expire; - spin_lock_init(&dd->lock); - spin_lock_init(&dd->zone_lock); /* We dispatch from request queue wide instead of hw queue */ blk_queue_flag_set(QUEUE_FLAG_SQ_SCHED, q); From patchwork Thu Jan 18 18:04:57 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jens Axboe X-Patchwork-Id: 13523086 Received: from mail-il1-f171.google.com (mail-il1-f171.google.com [209.85.166.171]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BC1302D609 for ; Thu, 18 Jan 2024 18:05:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705601154; cv=none; b=iFJanosd/JIyz9uBoqcp6riNVNPIUmwt2bTdsVsznUPUeai1vY8yH4bVM/j2l/oOZTyZ/ZAjh4t3J9Au1yeg8QYaItyptBSuQEq/ETIow3KFcMTrHQNyktGJLeRmSgBVFVhhl+xPgtbkzQ4sl/CIGH1a+eKmMIIB8hS1qdsaOj0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705601154; c=relaxed/simple; bh=XLtFh+4fWxIXKoubvDFOyDpiQ8Gh0Mc4F93R33jMV/o=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=tnLV+Fag73yYmdbUmxTt7JtnYDfJCLDQbVRLhF7HZiBCoQnXTBbvCwCwn4FGGHswJLQe+w2XK/KmiCx+M8ceWT8XtIo4yIFWok0kP1uoKn729KxwyBjF4Ruks8dfcNEWVbZtcM9mGMGDII7sl9eprwIvwFkSn6c23pWcBSTwAX8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=kernel.dk; spf=pass smtp.mailfrom=kernel.dk; dkim=pass (2048-bit key) header.d=kernel-dk.20230601.gappssmtp.com header.i=@kernel-dk.20230601.gappssmtp.com header.b=CGPwfjvt; arc=none smtp.client-ip=209.85.166.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=kernel.dk Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=kernel.dk Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel-dk.20230601.gappssmtp.com header.i=@kernel-dk.20230601.gappssmtp.com header.b="CGPwfjvt" Received: by mail-il1-f171.google.com with SMTP id e9e14a558f8ab-36191ee7be4so3287065ab.0 for ; Thu, 18 Jan 2024 10:05:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel-dk.20230601.gappssmtp.com; s=20230601; t=1705601151; x=1706205951; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=EW0ywMN8IyqUZ7Mc9p1SkRGgoUcTSdaHcbYxrzonAOc=; b=CGPwfjvt73bc2EADdljcienissHnQMu8JzmB0SEiIruECHeUdLY6AUT+7RQZYukaFa 3kVw6kZ5vFbMWsDScrU/7vVoo8Q2/3B+zbydssVLLQfIq8BwR8RQj0lbhLQs7HSuhLhu F1r5HIkyS31OyFsTBSwRY/B+qsBTyvPzOHZuGSw8tRP0afGmxGpG3F8QSFfGPn8X0+1d h+yUBMORXS92lI1BHXM+rYtlipuw6go3oexNrIcnOSkVO9Yi8gaBjQxH1G6u6AdkMKjU ob7mjxjtdp/GFGmeZ0OAx/1dJdJ+Ez9BMRiTAvEIVI5gUKUeh4fFUiT6yDXqO2bQYHk0 aZnQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705601151; x=1706205951; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=EW0ywMN8IyqUZ7Mc9p1SkRGgoUcTSdaHcbYxrzonAOc=; b=Elo0A2jLpOf0k7bjFH0V9q9hLYgJYX7dO+iZJYm6KKXPo6EODZi2C9+7jN7dVeFosF s3RN2mTcmogHQ6AdivNUVdfNdQ2DNAUHATGCVPiue2XMKJvXruJHMttYretWb7TzXJKP aJUBd+Isjn7hadZbPC/S7vA2bIp93wFFOqo+Tm5gXxzr4fOoAib7ZwWrx9u1n7p3ykce iUTyoZhERX8lKCz3WQhN98lerGEYemaIviJUGk/1OOrRI/yEO3NiYa7iDGbP1K5nKblo Zlbm314GYOUX2He2E+EqBeJq8QyrBKskb7Ia50LPlrT+EBc8YQ8n2/skX5zV6sV09ktd bf5A== X-Gm-Message-State: AOJu0YxtUO8ahqEBfFmA4/AwcMz6gMdpk4UnrVGiovoI/qOJSM/4Afar vNsLakCXGc+4141aWSW7P8r8oxOShXdc/LSH3n+6Cah4t65Qmq3T4Vhzmq4gRan/Kbudg18AmoY ZwXE= X-Google-Smtp-Source: AGHT+IG/jgKLRweZvUu7L0pt8hUfn+VsBI2YsMseH4fp9pXo5J973t8kYVszGMq/GkIR4XEWQVbjoA== X-Received: by 2002:a92:cda2:0:b0:35f:fa79:644 with SMTP id g2-20020a92cda2000000b0035ffa790644mr35297ild.3.1705601151492; Thu, 18 Jan 2024 10:05:51 -0800 (PST) Received: from localhost.localdomain ([96.43.243.2]) by smtp.gmail.com with ESMTPSA id bq7-20020a056e02238700b0036088147a06sm4981873ilb.1.2024.01.18.10.05.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 18 Jan 2024 10:05:49 -0800 (PST) From: Jens Axboe To: linux-block@vger.kernel.org Cc: bvanassche@acm.org, Jens Axboe Subject: [PATCH 2/2] block/mq-deadline: fallback to per-cpu insertion buckets under contention Date: Thu, 18 Jan 2024 11:04:57 -0700 Message-ID: <20240118180541.930783-3-axboe@kernel.dk> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240118180541.930783-1-axboe@kernel.dk> References: <20240118180541.930783-1-axboe@kernel.dk> Precedence: bulk X-Mailing-List: linux-block@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 If we attempt to insert a list of requests but someone else is already running an insertion, then fallback to queueing it internally and let the existing inserter finish the operation. Signed-off-by: Jens Axboe --- block/mq-deadline.c | 118 +++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 110 insertions(+), 8 deletions(-) diff --git a/block/mq-deadline.c b/block/mq-deadline.c index 9e0ab3ea728a..eeeaaff189e1 100644 --- a/block/mq-deadline.c +++ b/block/mq-deadline.c @@ -81,8 +81,17 @@ struct dd_per_prio { enum { DD_DISPATCHING = 0, + DD_INSERTING = 1, }; +#define DD_CPU_BUCKETS 32 +#define DD_CPU_BUCKETS_MASK (DD_CPU_BUCKETS - 1) + +struct dd_bucket_list { + struct list_head list; + spinlock_t lock; +} ____cacheline_aligned_in_smp; + struct deadline_data { /* * run time data @@ -94,6 +103,9 @@ struct deadline_data { unsigned long run_state; + atomic_t insert_seq; + struct dd_bucket_list bucket_lists[DD_CPU_BUCKETS]; + struct dd_per_prio per_prio[DD_PRIO_COUNT]; /* Data direction of latest dispatched request. */ @@ -711,7 +723,7 @@ static int dd_init_sched(struct request_queue *q, struct elevator_type *e) struct deadline_data *dd; struct elevator_queue *eq; enum dd_prio prio; - int ret = -ENOMEM; + int i, ret = -ENOMEM; eq = elevator_alloc(q, e); if (!eq) @@ -725,6 +737,12 @@ static int dd_init_sched(struct request_queue *q, struct elevator_type *e) spin_lock_init(&dd->lock); spin_lock_init(&dd->zone_lock); + atomic_set(&dd->insert_seq, 0); + + for (i = 0; i < DD_CPU_BUCKETS; i++) { + INIT_LIST_HEAD(&dd->bucket_lists[i].list); + spin_lock_init(&dd->bucket_lists[i].lock); + } for (prio = 0; prio <= DD_PRIO_MAX; prio++) { struct dd_per_prio *per_prio = &dd->per_prio[prio]; @@ -876,6 +894,67 @@ static void dd_insert_request(struct blk_mq_hw_ctx *hctx, struct request *rq, } } +static void dd_dispatch_from_buckets(struct deadline_data *dd, + struct list_head *list) +{ + int i; + + for (i = 0; i < DD_CPU_BUCKETS; i++) { + struct dd_bucket_list *bucket = &dd->bucket_lists[i]; + + if (list_empty_careful(&bucket->list)) + continue; + spin_lock(&bucket->lock); + list_splice_init(&bucket->list, list); + spin_unlock(&bucket->lock); + } +} + +/* + * If we can grab the dd->lock, then just return and do the insertion as per + * usual. If not, add to one of our internal buckets, and afterwards recheck + * if if we should retry. + */ +static bool dd_insert_to_bucket(struct deadline_data *dd, + struct list_head *list, int *seq) + __acquires(&dd->lock) +{ + struct dd_bucket_list *bucket; + int next_seq; + + *seq = atomic_read(&dd->insert_seq); + + if (spin_trylock(&dd->lock)) + return false; + if (!test_bit(DD_INSERTING, &dd->run_state)) { + spin_lock(&dd->lock); + return false; + } + + *seq = atomic_inc_return(&dd->insert_seq); + + bucket = &dd->bucket_lists[get_cpu() & DD_CPU_BUCKETS_MASK]; + spin_lock(&bucket->lock); + list_splice_init(list, &bucket->list); + spin_unlock(&bucket->lock); + put_cpu(); + + /* + * If seq still matches, we should be safe to just exit with the + * pending requests queued in a bucket. + */ + next_seq = atomic_inc_return(&dd->insert_seq); + if (next_seq == *seq + 1) + return true; + + /* + * Seq changed, be safe and grab the lock and insert. Don't update + * sequence, so that we flusht the buckets too. + */ + spin_lock(&dd->lock); + return false; +} + /* * Called from blk_mq_insert_request() or blk_mq_dispatch_plug_list(). */ @@ -886,16 +965,39 @@ static void dd_insert_requests(struct blk_mq_hw_ctx *hctx, struct request_queue *q = hctx->queue; struct deadline_data *dd = q->elevator->elevator_data; LIST_HEAD(free); + int seq; - spin_lock(&dd->lock); - while (!list_empty(list)) { - struct request *rq; + /* + * If dispatch is busy and we ended up adding to our internal bucket, + * then we're done for now. + */ + if (dd_insert_to_bucket(dd, list, &seq)) + return; + + set_bit(DD_INSERTING, &dd->run_state); + do { + int next_seq; + + while (!list_empty(list)) { + struct request *rq; + + rq = list_first_entry(list, struct request, queuelist); + list_del_init(&rq->queuelist); + dd_insert_request(hctx, rq, flags, &free); + } + + /* + * If sequence changed, flush internal buckets + */ + next_seq = atomic_inc_return(&dd->insert_seq); + if (next_seq == seq + 1) + break; + seq = next_seq; + dd_dispatch_from_buckets(dd, list); + } while (1); - rq = list_first_entry(list, struct request, queuelist); - list_del_init(&rq->queuelist); - dd_insert_request(hctx, rq, flags, &free); - } spin_unlock(&dd->lock); + clear_bit(DD_INSERTING, &dd->run_state); blk_mq_free_requests(&free); }