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 23099 invoked from network); 2 Mar 2022 01:49:23 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 2 Mar 2022 01:49:23 -0000 Received: (qmail 3371 invoked by uid 550); 2 Mar 2022 01:49:17 -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 3291 invoked from network); 2 Mar 2022 01:49:15 -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=/tSEsfh4fECwb8eBJ+X/5D3dHBFEcfVS5nQnHrBSB4k=; b=ctllcv9CZTO/St3miJvYACb91RHBBrL8uHgpgSojy+pe1dTdyQ9G7D+5kfz1FTxji2 rDokEvKvMwcRkhnGb8IDPCyw4UjE/rQbCjNGzV6fipGb+QTyzlCFmwzeQPXZYVTZCicf gH0mz0a4VCxV81LnDu18c9y2yAdmyP2O5xm2IZof2iKhg2pbnBs3PcePdY2aNVptB96/ uDlY8AKjTA6KJ3FCnu9SAIMckmFpIv+IVck1B1/t17JOVADD4HCYVGebQ6o8dMBCJGHk o8qWm7OJaKnudydG+ObTzlNCpBDQF171Kz3AHf3xGacEOTLeSQViFUdgP72ba6TFVMzg CdKg== 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=/tSEsfh4fECwb8eBJ+X/5D3dHBFEcfVS5nQnHrBSB4k=; b=a6WgDDWd/Bdd1ANT/S9z5FxqcvIB5Afh23deWLE/2Plyo+iDQoyBWQ6VvfmqRqpp24 DK90V/50J2gYvgfrqISdcfLke9DfimKMqAk7B4VtK8vnGADSGC3BRaK/+GwG+sK9O8Rc txaNWNDm4k/S+3Y3DIlZvfdjJIU/e1/M+MN8Hx3V9ddy0e71oK6eYcvVtS9dOb6m3LkS EBQpQJea0ctQwq183KRF1ii8zSVrxyA6s75auZLYLEqV7LTkDH0/M26yYTo9SghohEtp zBeuWPfSKQDzEoFVNHXwuiPx6yDlqx0gdZ6Yb1wxVbQgGpe918VuYNU51/yHnW4IeZc7 O2/g== X-Gm-Message-State: AOAM533aDVzxHU7E2CA+WV3CmFX5akDiaSgo5VSjDMsTzd3BK4OYi1K2 8uMM0EwO3sPhE8GKeQMMK8tp9Sb4UsnoLNE2s1zR5XdI X-Google-Smtp-Source: ABdhPJymdh/CmC6LU0y444Zxt8GcY0fF2cZdAhZfSuOwxIGjUJoEiByabLgji/VO1uuAxE2CQLSkyvVkFXZ+E80Bweg= X-Received: by 2002:a67:f7d5:0:b0:31c:f77:2ed5 with SMTP id a21-20020a67f7d5000000b0031c0f772ed5mr11590369vsp.26.1646185742193; Tue, 01 Mar 2022 17:49:02 -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: From: Lee Shallis Date: Wed, 2 Mar 2022 01:44:38 +0000 Message-ID: To: musl@lists.openwall.com Content-Type: multipart/mixed; boundary="000000000000668f9a05d9327c02" Subject: Re: [musl] Suggestion for thread safety --000000000000668f9a05d9327c02 Content-Type: text/plain; charset="UTF-8" Welp, I think I finally managed to fix my implementation, wasn't quite what I had in mind but it was the only method that seemed to work without the bulky code pthread_mutex_lock falls to, it is however slightly slower so I would treat it as a fallback for systems that don't provide a mutex for now, the solution I ended up with utilises kill( getpid(), SIGCONT ) & an additional member to identify which thread managed to get their pid_t in at the time of the claim. On Mon, 28 Feb 2022 at 16:07, Lee Shallis wrote: > > 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 --000000000000668f9a05d9327c02 Content-Type: text/x-csrc; charset="US-ASCII"; name="lock.c" Content-Disposition: attachment; filename="lock.c" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_l08w8q160 I2RlZmluZSBfR05VX1NPVVJDRQojaW5jbHVkZSA8bGltaXRzLmg+CiNpbmNsdWRlIDxzdGRib29s Lmg+CiNpbmNsdWRlIDx1bmlzdGQuaD4KI2luY2x1ZGUgPGVycm5vLmg+CiNpbmNsdWRlIDxsaW51 eC90eXBlcy5oPgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8c3lzL3Jlc291cmNlLmg+CiNp bmNsdWRlIDxzY2hlZC5oPgojaW5jbHVkZSA8c2V0am1wLmg+CiNpbmNsdWRlIDxzaWduYWwuaD4K I2luY2x1ZGUgPHB0aHJlYWQuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8c3RkbGli Lmg+CiNpbmNsdWRlIDxzdGRpby5oPgoKLy8jZGVmaW5lIFBSSU5UX0xPQ0tTCi8vI2RlZmluZSBQ UklOVF9BVFRFTVBUUwovKiBTZWNvbmRzICovCiNkZWZpbmUgVElNRURfVEVTVCAwCi8qIExvb3Bz LCBub3QgdXNlZCBpZiBUSU1FRF9URVNUICE9IDAgKi8KI2RlZmluZSBUUklFU19UT0RPIENMT0NL U19QRVJfU0VDCgp0eXBlZGVmIHVuc2lnbmVkIGludCB1aW50Owp0eXBlZGVmIHVuc2lnbmVkIGxv bmcgaW50IHVsb25nOwp0eXBlZGVmIHN0cnVjdCBfTE9DSwp7Cgl1aW50IG51bTsKCXZvaWQgKnVk OwoJc3RydWN0IHRpbWVzcGVjIHRzOwoJdm9sYXRpbGUgcGlkX3QgdGlkOwoJdm9sYXRpbGUgcGlk X3QgdHJ5aW5nOwp9IExPQ0s7Cgp2b2xhdGlsZSBMT0NLICpfc2hhcmVkID0gTlVMTDsKCnZvaWQg bG9ja19oYW5kbGVyKCBpbnQgc2lnbmFsICkKewoJLyogV2UgZG9uJ3Qgd2FudCB0aGUgcG9pbnRl ciB3ZSdyZSB3b3JraW5nIHdpdGggdG8gY2hhbmdlIG1pZHdheQoJICogdGhyb3VnaCBzbyB3ZSB0 YWtlIGEgY29weSB0aGVuIHdvcmsgd2l0aCB0aGF0ICovCgl2b2xhdGlsZSBMT0NLICpzaGFyZWQg PSBfc2hhcmVkOwoJKHZvaWQpc2lnbmFsOwoKCWlmICggIShzaGFyZWQtPnRpZCkgKQoJCXNoYXJl ZC0+dGlkID0gc2hhcmVkLT50cnlpbmc7CiNpZmRlZiBQUklOVF9BVFRFTVBUUwoJZmxvY2tmaWxl KCBzdGRvdXQgKTsKCXByaW50ZiggIlRocmVhZCAlbHUgYXR0ZW1wdGVkIGxvY2tcbiIsICh1bG9u Zykoc2hhcmVkLT50cnlpbmcpICk7CglmdW5sb2NrZmlsZSggc3Rkb3V0ICk7CiNlbmRpZgp9Cgpp bnQgTG9ja1NpRGF0YSggTE9DSyAqc2hhcmVkICkKewoJaW50IGNvbnN0IHNpZyA9IFNJR0NPTlQ7 CglwaWRfdCB0aWQgPSBnZXR0aWQoKSwgd2FzOwoJc3RydWN0IHNpZ2FjdGlvbiB0aGlzID0ge05V TEx9LCBwcmV2ID0ge05VTEx9OwoKCS8qIFBvc3NpYmxlIG91ciBzaWduYWwgaGFuZGxlciB3aWxs IGJlIGNhbGxlZCBiZWZvcmUgX3NoYXJlZCBpcyBub3QKCSAqIE5VTEwgc28gd2Ugc2V0IGl0IHBy aW9yIHRvIHRyeWluZyB0aGVuIGNvbnRpbnVlIG9uICovCglfc2hhcmVkID0gc2hhcmVkOwoJdGhp cy5zYV9oYW5kbGVyID0gbG9ja19oYW5kbGVyOwoKCXNpZ2FjdGlvbiggc2lnLCAmdGhpcywgJnBy ZXYgKTsKCglmb3IgKCB3YXMgPSBzaGFyZWQtPnRpZDsgd2FzICE9IHRpZDsgd2FzID0gc2hhcmVk LT50aWQgKQoJewoJCWlmICggIXdhcyApCgkJewoJCQlzaGFyZWQtPnRyeWluZyA9IHRpZDsKCQkJ X3NoYXJlZCA9IHNoYXJlZDsKCQkJa2lsbCggZ2V0cGlkKCksIHNpZyApOwoJCX0KCX0KCglzaWdh Y3Rpb24oIHNpZywgJnByZXYsICZ0aGlzICk7CgoJY2xvY2tfZ2V0dGltZSggQ0xPQ0tfUFJPQ0VT U19DUFVUSU1FX0lELCAmKHNoYXJlZC0+dHMpICk7CglzaGFyZWQtPm51bSsrOwoKI2lmZGVmIFBS SU5UX0xPQ0tTCglmbG9ja2ZpbGUoIHN0ZG91dCApOwoJcHJpbnRmKCAiVGhyZWFkICVsdSB0b29r IGxvY2tcbiIsICh1bG9uZyl0aWQgKTsKCWZ1bmxvY2tmaWxlKCBzdGRvdXQgKTsKI2VuZGlmCgly ZXR1cm4gMDsKfQoKaW50IEZyZWVTaURhdGEoIExPQ0sgKnNoYXJlZCApCnsKCXBpZF90IHRpZCA9 IGdldHRpZCgpOwoJaWYgKCBzaGFyZWQtPnRpZCAhPSB0aWQgKQoJCXJldHVybiAwOwoJc2hhcmVk LT5udW0tLTsKCWlmICggc2hhcmVkLT5udW0gKQoJCXJldHVybiAwOwojaWZkZWYgUFJJTlRfTE9D S1MKCWZsb2NrZmlsZSggc3Rkb3V0ICk7CglwcmludGYoICJUaHJlYWQgJWx1IHJlbGVhc2VkIGxv Y2tcbiIsICh1bG9uZyl0aWQgKTsKCWZ1bmxvY2tmaWxlKCBzdGRvdXQgKTsKI2VuZGlmCglzaGFy ZWQtPnRpZCA9IChwaWRfdCkwOwoJcmV0dXJuIDA7Cn0KCkxPQ0sgdGxvY2sgPSB7MH07CnB0aHJl YWRfbXV0ZXhfdCBtdXRleDsKCnR5cGVkZWYgaW50ICgqbG9ja19jYikoIHZvaWQgKnVkICk7CnR5 cGVkZWYgc3RydWN0IF9URVNUCnsKCXZvbGF0aWxlIHVpbnQgcXVpdDsKCXZvbGF0aWxlIHVpbnQg ZGF0YTsKCXZvaWQgKnVkOwoJY2hhciAqbmFtZTsKCWxvY2tfY2IgbG9jazsKCWxvY2tfY2IgZnJl ZTsKfSBURVNUOwoKdm9pZCogQWJvcnQoIFRFU1QgKnRlc3QsIHVpbnQgZ290LCB1aW50IGV4cGVj dGVkLCBjbG9ja190IHN0YXJ0ICkKewoJdWxvbmcgdGlja3MgPSAodWxvbmcpKGNsb2NrKCkgLSBz dGFydCk7Cgl0ZXN0LT5mcmVlKCB0ZXN0LT51ZCApOwoJZmxvY2tmaWxlKCBzdGRvdXQgKTsKCXBy aW50ZgoJKAoJCSJUaHJlYWQgJWx1IChsb2NrJXMpIGVuZGVkIGF0ICVsdSB0aWNrcywgIgoJCSJn b3QgPSAldSwgZXhwZWN0ZWQgJXVcbiIsCgkJKHVsb25nKWdldHRpZCgpLCB0ZXN0LT5uYW1lLCB0 aWNrcywgZ290LCBleHBlY3RlZAoJKTsKCWZ1bmxvY2tmaWxlKCBzdGRvdXQgKTsKCWV4aXQoMSk7 CgkvKiBQcmV2ZW50cyBnb2luZyBmdXJ0aGVyIHRoYW4gZXhwZWN0ZWQgKi8KCXJldHVybiB0ZXN0 Owp9Cgp2b2lkKiB0aHJlYWQoIHZvaWQgKnVkICkKewoJVEVTVCAqdGVzdCA9IHVkOwoJdWludCBn b3QsIGV4cGVjdGVkOwoJcGlkX3QgdGlkID0gZ2V0dGlkKCk7CgljbG9ja190IHN0YXJ0ID0gY2xv Y2soKSwgZW5kID0gc3RhcnQgKyAoQ0xPQ0tTX1BFUl9TRUMgKiBUSU1FRF9URVNUKTsKCXN0cnVj dCB0aW1lc3BlYyB0cyA9IHswfTsKCXRzLnR2X25zZWMgPSAxOwoJKHZvaWQpdWQ7CgoJZmxvY2tm aWxlKCBzdGRvdXQgKTsKCXByaW50ZiggIlRocmVhZCAlbHUgKGxvY2slcylcbiIsICh1bG9uZyl0 aWQsIHRlc3QtPm5hbWUgKTsKCWZ1bmxvY2tmaWxlKCBzdGRvdXQgKTsKCiNpZiBUSU1FRF9URVNU Cgl3aGlsZSAoIGVuZCA+IGNsb2NrKCkgKQojZWxzZQoJd2hpbGUgKCB0ZXN0LT5xdWl0IDwgVFJJ RVNfVE9ETyApCiNlbmRpZgoJewoJCXRlc3QtPmxvY2soIHRlc3QtPnVkICk7CgoJCWV4cGVjdGVk ID0gMDsKCQlnb3QgPSAodGVzdC0+ZGF0YSkrKzsKCQlpZiAoZ290ICE9IGV4cGVjdGVkKQoJCQly ZXR1cm4gQWJvcnQoIHRlc3QsIGdvdCwgZXhwZWN0ZWQsIHN0YXJ0ICk7CgoJCWNsb2NrX25hbm9z bGVlcChDTE9DS19NT05PVE9OSUMsIDAsICZ0cywgMCk7CgoJCWV4cGVjdGVkID0gMTsKCQlnb3Qg PSAodGVzdC0+ZGF0YSktLTsKCQlpZiAoZ290ICE9IGV4cGVjdGVkKQoJCQlyZXR1cm4gQWJvcnQo IHRlc3QsIGdvdCwgZXhwZWN0ZWQsIHN0YXJ0ICk7CgoJCXRlc3QtPnF1aXQrKzsKCQl0ZXN0LT5m cmVlKCB0ZXN0LT51ZCApOwoJfQoKCWVuZCA9IGNsb2NrKCk7CglmbG9ja2ZpbGUoIHN0ZG91dCAp OwoJcHJpbnRmCgkoCgkJImxvY2slcyAoJWx1KSB0b29rICU1bHUgY2xvY2sgdGlja3NcbiIsCgkJ dGVzdC0+bmFtZSwgKHVsb25nKXRpZCwgKHVsb25nKShlbmQgLSBzdGFydCkKCSk7CglmdW5sb2Nr ZmlsZSggc3Rkb3V0ICk7CglyZXR1cm4gdWQ7Cn0KCmludCBtYWluKCkKewoJcHRocmVhZF90IHB0 OwoJaW50IGk7CgoJVEVTVCAqdGVzdDsKCVRFU1QgdGVzdHNbMl0gPSB7ezB9fTsKCglzZXRidWYo c3Rkb3V0LE5VTEwpOwoKCXRlc3QgPSB0ZXN0czsKCXRlc3QtPnVkID0gJnRsb2NrOwoJdGVzdC0+ bmFtZSA9ICJzaWRhdGEiOwoJdGVzdC0+bG9jayA9IChsb2NrX2NiKUxvY2tTaURhdGE7Cgl0ZXN0 LT5mcmVlID0gKGxvY2tfY2IpRnJlZVNpRGF0YTsKCgl0ZXN0ID0gdGVzdHMgKyAxOwoJdGVzdC0+ dWQgPSAmbXV0ZXg7Cgl0ZXN0LT5uYW1lID0gIm11dGV4IjsKCXRlc3QtPmxvY2sgPSAobG9ja19j YilwdGhyZWFkX211dGV4X2xvY2s7Cgl0ZXN0LT5mcmVlID0gKGxvY2tfY2IpcHRocmVhZF9tdXRl eF91bmxvY2s7CgoJZm9yIChpID0gMDsgaSA8IDI7IGkrKykKCXsKCQlpZiAoKGVycm5vID0gcHRo cmVhZF9jcmVhdGUoJnB0LCAwLCB0aHJlYWQsIHRlc3RzKSkgIT0gMCApCgkJewoJCQlmbG9ja2Zp bGUoIHN0ZG91dCApOwoJCQlwcmludGYoInB0aHJlYWRfY3JlYXRlIGZhaWxlZDogJW1cbiIpOwoJ CQlmdW5sb2NrZmlsZSggc3Rkb3V0ICk7CgkJCXJldHVybiAxOwoJCX0KCgkJaWYgKChlcnJubyA9 IHB0aHJlYWRfY3JlYXRlKCZwdCwgMCwgdGhyZWFkLCB0ZXN0cyArIDEpKSAhPSAwICkKCQl7CgkJ CWZsb2NrZmlsZSggc3Rkb3V0ICk7CgkJCXByaW50ZigicHRocmVhZF9jcmVhdGUgZmFpbGVkOiAl bVxuIik7CgkJCWZ1bmxvY2tmaWxlKCBzdGRvdXQgKTsKCQkJcmV0dXJuIDE7CgkJfQoJfQoKCXB0 aHJlYWRfZXhpdCgwKTsKCXB0aHJlYWRfbXV0ZXhfZGVzdHJveSggJm11dGV4ICk7Cn0K --000000000000668f9a05d9327c02--