Received: by 2002:a05:6a10:5bc5:0:0:0:0 with SMTP id os5csp5542280pxb; Sun, 7 Nov 2021 14:47:41 -0800 (PST) X-Google-Smtp-Source: ABdhPJwc9yqnFjWTshtue/SB77zOJI85rPN2K4VYcDcSeVZu+tAzSig23Fv2UcQ+0UhQ29MqkZ8w X-Received: by 2002:a50:935e:: with SMTP id n30mr28503615eda.293.1636325261424; Sun, 07 Nov 2021 14:47:41 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1636325261; cv=none; d=google.com; s=arc-20160816; b=ldxSLH1PHyntDa5YxsAjtORD7erBBeqgEKGcX8d/oybMG+UpVGrf7JmC39fvogMqij AmpsdeBOqgr5z7m5rdiqDQNDVA3hFdoOV1Lyx5Ub0RaypdSzAac1F7UnadCpAszh6g0w 7hTATkiWu92B372Wbwz7rUUCYtONC6ATyNWzSznaIwxywUmAwiAPR8TZCDldvgspTRfz xKi9WmQaJnGlXZr+1f7sWkK13X/LdYxvEJxubpj3JQbcSNpIy2PfZB5joRYaTEX8Aeh/ jU+fba2wP1CtsyXntCfTRSEzU1x/ZcFJdtxDVeA+tP2kh6l+27HiZ51FXea/8V7kaT0S aAZg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:in-reply-to:content-disposition:mime-version :references:message-id:subject:cc:to:from:dkim-signature:date; bh=RS/Nz/UG56GlGiRm7O/muf8wz5uSzD19AWx+yQ3NlEo=; b=ITHJXYcYXVqM0EdhrUGl21xjLY2Qox0a6ilw1cHNQQ6SWGWiEaLnloOz0OvgauupNw 9kmTN45C8s+9CKopptGjnjsajW/CL+ZBE5rmKnpDb4AvZqYfZS4JQJtzwhZi63LaZ68W 2zaVD/XWCc1M/MmBH19AxbaH9CXkrnhGJQMv2789KktPJLkfRC+tA9n+xJ1cho2G1/nI GctCIyjoeabOSDfCemqHGDhGVza3FHYpIHkr6YOXBeLdA28Vl3xk/pAMT37Bvt0hB5E1 vnPCpOqSGVFm+Z58HXbagcGpqEG8ue4qEFhU5NU+j+ena19ZI7+WwYy6UVnPPDVWQf1Z 5lAg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b=G8+4iXdm; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Return-Path: Received: from vger.kernel.org (vger.kernel.org. [23.128.96.18]) by mx.google.com with ESMTP id j16si28020659edj.201.2021.11.07.14.47.18; Sun, 07 Nov 2021 14:47:41 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18; Authentication-Results: mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b=G8+4iXdm; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234963AbhKGQgF (ORCPT + 99 others); Sun, 7 Nov 2021 11:36:05 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60014 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229966AbhKGQgE (ORCPT ); Sun, 7 Nov 2021 11:36:04 -0500 Received: from out2.migadu.com (out2.migadu.com [IPv6:2001:41d0:2:aacc::]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 88E43C061570; Sun, 7 Nov 2021 08:33:21 -0800 (PST) Date: Mon, 8 Nov 2021 00:34:00 +0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1636302799; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=RS/Nz/UG56GlGiRm7O/muf8wz5uSzD19AWx+yQ3NlEo=; b=G8+4iXdmP/uX9z5jnC2n5GBIzfBb+e/KpFD9HAleCwzk6ibUcXgsIj2a6HgqhU0YTDoi9U BYRRYTKTJBzN6G+gZ/ZwHnDh1MHVb5cX144Hvoa/14Pv1Bog9CWmp8FdYGnQoduqeg1EgN aW1XXWa/2iIafq4PyJ4LLPHtX1NKKG4= X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. From: Tao Zhou To: Peter Oskolkov Cc: Peter Zijlstra , Ingo Molnar , Thomas Gleixner , Andrew Morton , Dave Hansen , Andy Lutomirski , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-api@vger.kernel.org, Paul Turner , Ben Segall , Peter Oskolkov , Andrei Vagin , Jann Horn , Thierry Delisle , Tao Zhou Subject: Re: [PATCH v0.8 4/6] sched/umcg, lib/umcg: implement libumcg Message-ID: References: <20211104195804.83240-1-posk@google.com> <20211104195804.83240-5-posk@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20211104195804.83240-5-posk@google.com> X-Migadu-Flow: FLOW_OUT X-Migadu-Auth-User: tao.zhou@linux.dev Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, Nov 04, 2021 at 12:58:02PM -0700, Peter Oskolkov wrote: > +/* Update the state variable, set new timestamp. */ > +static bool umcg_update_state(uint64_t *state, uint64_t *prev, uint64_t next) > +{ > + uint64_t prev_ts = (*prev) >> (64 - UMCG_STATE_TIMESTAMP_BITS); > + struct timespec now; > + uint64_t next_ts; > + int res; > + > + /* > + * clock_gettime(CLOCK_MONOTONIC, ...) takes less than 20ns on a > + * typical Intel processor on average, even when run concurrently, > + * so the overhead is low enough for most applications. > + * > + * If this is still too high, `next_ts = prev_ts + 1` should work > + * as well. The only real requirement is that the "timestamps" are > + * uniqueue per thread within a reasonable time frame. > + */ > + res = clock_gettime(CLOCK_MONOTONIC, &now); > + assert(!res); > + next_ts = (now.tv_sec * NSEC_PER_SEC + now.tv_nsec) >> > + UMCG_STATE_TIMESTAMP_GRANULARITY; > + > + /* Cut higher order bits. */ > + next_ts &= ((1ULL << UMCG_STATE_TIMESTAMP_BITS) - 1); This is the right cut.. The same to the kernel side. > + > + if (next_ts == prev_ts) > + ++next_ts; > + > +#ifndef NDEBUG > + if (prev_ts > next_ts) { > + fprintf(stderr, "%s: time goes back: prev_ts: %lu " > + "next_ts: %lu diff: %lu\n", __func__, > + prev_ts, next_ts, prev_ts - next_ts); > + } > +#endif > + > + /* Remove old timestamp, if any. */ > + next &= ((1ULL << (64 - UMCG_STATE_TIMESTAMP_BITS)) - 1); > + > + /* Set the new timestamp. */ > + next |= (next_ts << (64 - UMCG_STATE_TIMESTAMP_BITS)); > + > + /* > + * TODO: review whether memory order below can be weakened to > + * memory_order_acq_rel for success and memory_order_acquire for > + * failure. > + */ > + return atomic_compare_exchange_strong_explicit(state, prev, next, > + memory_order_seq_cst, memory_order_seq_cst); > +} > + > +static void task_unlock(struct umcg_task_tls *task, uint64_t expected_state, > + uint64_t new_state) > +{ > + bool ok; > + uint64_t next; > + uint64_t prev = atomic_load_explicit(&task->umcg_task.state_ts, > + memory_order_acquire); > + > + next = ((prev & ~UMCG_TASK_STATE_MASK_FULL) | new_state) & ~UMCG_TF_LOCKED; Use UMCG_TASK_STATE_MASK instead and the other state flag can be checked. All others places that use UMCG_TASK_STATE_MASK_FULL to mask to check the task state may seems reasonable if the state flag not allowed to be set when we check that task state, otherwise use UMCG_TASK_STATE_MASK will be enough. Not sure. Thanks, Tao > + assert(next != prev); > + assert((prev & UMCG_TASK_STATE_MASK_FULL & ~UMCG_TF_LOCKED) == expected_state); > + > + ok = umcg_update_state(&task->umcg_task.state_ts, &prev, next); > + assert(ok); > +}