From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.1 required=5.0 tests=DKIM_ADSP_CUSTOM_MED, DKIM_INVALID,DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 22846 invoked from network); 28 Feb 2022 16:11:38 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 28 Feb 2022 16:11:38 -0000 Received: (qmail 29938 invoked by uid 550); 28 Feb 2022 16:11:36 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 29906 invoked from network); 28 Feb 2022 16:11:35 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:reply-to:from:date:message-id :subject:to; bh=LC/hCw8sfnobCpiH/Jpt5EljCKgPqYZl/A9jfLOZMF8=; b=aeh+xbigongHZq/17KkeKZvyMovBmNINO3sK9c9q21NHzeZvZQ8+7c/P91mzZzDCyU 6JPb+HL8HCAJngITUtvxgNVFtPoxVbMsnhizofVSIXPCH/W9aM5Xw8CYuaqtoKJ6QErF J0TiF1N+OPg0oUBCJM87oVImZe/TxXiueyeX2G20Wyai9Fb5nrLJN5qxtcFkJ4gK4CCW 5TJ9+/HSFMfIqJaE2r4v3rsi2mdPCKu4/ErkoLjF8V0/T1Sob1HuK1ldLY8FxdMmlVis jQVYiopUOFDcVaAqbHnt7ok3rrcIQ70B2rVwnD2K5icgVVISzThlkubI2YTgozs0cpx4 eSAw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:reply-to :from:date:message-id:subject:to; bh=LC/hCw8sfnobCpiH/Jpt5EljCKgPqYZl/A9jfLOZMF8=; b=QH7Dr43ChYP6/SzRDCaZbYZcQJnfNH91EKelZ/L4yWa0L2rc8fa7fqvXEOS1zQAkML YrvXZyzyw2WtwnvLiC+8lshrpmANx8u5Tji+KxkdZZoqBmld9l4J3840y/VJxY3d9yQr fWzPFIC+V0tP6cIO18TU3xh9kFhV9tl6S0JpVP/NYriH04565Bzb4fy7gStOiNFpxrov KPDIj33bivXZQsRg9gjXHRdC83p7fnxL2CMM8G4iZQj7SSitzoNW3jwz1Vk+LYVIQkWA rdjgn9yBFQSsNtefmkD/XrEvhtq3HnfKsciv6ZZkWJU69WeTqivHelCFgn8byB1sRKJO 8PiA== X-Gm-Message-State: AOAM530GZzZ9+eGF/Vpaei7sfiGeWBihIm5277p6bKRll8V7emNXHOhX OVwZk53rmg2rUg8I4HfsVXarWSgQSF3pblnpTtoQWHDJ X-Google-Smtp-Source: ABdhPJw4P0GSnZxof1H22RaqR7ObbmC6AEpzg/fckC2WFGS7FRuskfnOPoCMg25040z0LMn+VTW6iL6jQv1+GlCH1jw= X-Received: by 2002:a9f:3183:0:b0:33c:741f:434e with SMTP id v3-20020a9f3183000000b0033c741f434emr8151628uad.7.1646064683629; Mon, 28 Feb 2022 08:11:23 -0800 (PST) MIME-Version: 1.0 References: <20220221174223.GA2079@voyager> <20220223185746.GB2079@voyager> <20220226123855.392c22acb208a966210c7af2@zhasha.com> <20220228094814.be34ddcf7be25724e8f8c21b@zhasha.com> <20220228165051.dd53c432ccd85517cb9513cd@zhasha.com> In-Reply-To: <20220228165051.dd53c432ccd85517cb9513cd@zhasha.com> From: Lee Shallis Date: Mon, 28 Feb 2022 16:07:02 +0000 Message-ID: To: musl@lists.openwall.com Content-Type: text/plain; charset="UTF-8" Subject: Re: [musl] Suggestion for thread safety On Mon, 28 Feb 2022 at 15:51, Joakim Sindholt wrote: > > On Mon, 28 Feb 2022 14:43:36 +0000, Lee Shallis wrote: > > Seems the wait just wasn't long enough, at about 4 yields onwards the > > results become consistent success, I've attached the file I did the > > experiments in, I even tried it under -O3 and no exits were > > encountered, so yes my method works, just needs a bit more wait time > > for extreme cases > > Between the lines > > if ( !(shared->tid) ) > and > > shared->tid = tid; > the kernel might suspend the running thread and allow the other to run, > or you might simply get unlucky and have the two threads do the checks > close enough to simultaneously that the memory hasn't been synchronized > yet. Either way you end up with both threads seeing that shared->tid is > zero and both of them writing their tids to it, and thus both enter the That's the point of the loop, to check it's the same as what they wrote, if it's not then it's either locked to another thread or empty, the point in doing the yield after the write is to allow that failure to occur, basically I'm using the race condition itself as the point of success, rather than expect the CPU to perform an atomic lock that could be just as broken as timing based locks, I already have my ideas on how to fix the need for many yields to need only 2, I'm about to try it now > critical section at the same time. And so the lock fails at the very > first hurdle: mutual exclusion. No amount of sleeping will make the bug > go away, only slightly more difficult to trigger. No it doesn't, think through the loop properly and you'll see that the concept is the best one to go with, implementation just needs a little work > The point of the clock_nanosleep call was to force a reschedule while > holding the lock. This also increases the runtime inside the lock which > in this case increases the likelihood that the thread trying to take the > lock will be waiting for it and end up racing with the thread that > currently has it when it unlocks and tries to relock it. How so? It still takes time for the jump condition to be evaluated and the call to LockSiData to start, the other thread will already be in the call loop ready to lock it, I designed this function specifically around the idea that multiple threads could see an empty tid at the same time, that's the reason for the yield call, so that all those writes get in before the execution resumes. > Now that you've inserted lots of sched_yield()s your lock is not only > still broken (in more ways than the one we've been trying to get you to > understand) but also extremely slow. > > As a hint for your future education: the first (and far from only) thing > you'll need is compare-and-swap, aka. CAS. > You can read up on this class of bugs if you'd like. It's called "Time > Of Check to Time Of Use" or "TOCTOU" for short. > > I didn't even need to poke at the code this time as the code you sent > breaks just the same on my machine. > > I hope you'll learn from this. I hope you'll learn to think through the code before you speak out of your ass, the concept is perfect, it's only that my implementation of that concept isn't