From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.71) id 1ZFR4I-0006mi-H5 for mharc-grub-devel@gnu.org; Wed, 15 Jul 2015 14:06:06 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:55530) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZFR4B-0006mV-Mk for grub-devel@gnu.org; Wed, 15 Jul 2015 14:06:05 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZFR4A-0003xX-B3 for grub-devel@gnu.org; Wed, 15 Jul 2015 14:05:59 -0400 Received: from mail-wi0-x22c.google.com ([2a00:1450:400c:c05::22c]:33141) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZFR4A-0003xE-3W for grub-devel@gnu.org; Wed, 15 Jul 2015 14:05:58 -0400 Received: by widic2 with SMTP id ic2so9472930wid.0 for ; Wed, 15 Jul 2015 11:05:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:subject:references :in-reply-to:content-type; bh=668p1CoPZuR8hLuG3Cju+P+6Po6u3d3r1KusTewhCcg=; b=hqrjOYimn+iyZlnbfdgvcEWMGVz2EMKMBnEVc1SwQSQqkEPPwaswvc0y2EPUzHpKYQ KhN667KHwbwxQ06Rr3ZMPpXXoyUhxSk09wMHB6pdYV8qM2K/+eIQUb2VIV2m2vJqdP9E FCrQ4//LpWuV0H0ghs/i+M+kZbJ5nfaiYGgrEgFzWMHRnwCIdfPKLW75XNgh96s5muKz Z5FF0hjmYSJtgy7t3ENrGWyxZAd0UdEqS9Ggd7PXaawnt2Nr60kWhXlISi+zVIZ3zCqe CKg2d3sCVvQ3KE3KvP2f2N9eQIMq8BqSgZRMDSjWlb/N2zdh2kFoRLVZ+aPBKeSgrZ9l q6MA== X-Received: by 10.180.88.99 with SMTP id bf3mr2553551wib.75.1436983557291; Wed, 15 Jul 2015 11:05:57 -0700 (PDT) Received: from ?IPv6:2620:0:105f:fd00:863a:4bff:fe50:abc4? ([2620:0:105f:fd00:863a:4bff:fe50:abc4]) by smtp.gmail.com with ESMTPSA id c3sm9063760wja.3.2015.07.15.11.05.56 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 15 Jul 2015 11:05:56 -0700 (PDT) Message-ID: <55A6A104.6060407@gmail.com> Date: Wed, 15 Jul 2015 20:05:56 +0200 From: =?UTF-8?B?VmxhZGltaXIgJ8+GLWNvZGVyL3BoY29kZXInIFNlcmJpbmVua28=?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Icedove/31.7.0 MIME-Version: 1.0 To: The development of GNU GRUB Subject: Re: [RFD] diskfilter stale RAID member detection vs. lazy scanning References: <20150628210655.6dfdbd9a@opensuse.site> In-Reply-To: <20150628210655.6dfdbd9a@opensuse.site> Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="2rmMWNbbv6HHU24Ab7aKdMrEfrrlehGxU" X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:400c:c05::22c X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list Reply-To: The development of GNU GRUB List-Id: The development of GNU GRUB List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 Jul 2015 18:06:05 -0000 This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --2rmMWNbbv6HHU24Ab7aKdMrEfrrlehGxU Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 28.06.2015 20:06, Andrei Borzenkov wrote: > I was looking at implementing detection of outdated RAID members. > Unfortunately it appears to be fundamentally incompatible with lazy > scanning as implemented currently by GRUB. We simply cannot stop > scanning for other copies of metadata once "enough" was seen. Because > any other disk may contain more actual copy which invalidates > everything seen up to this point. >=20 > So basically either we officially admit that GRUB is not able to detect= > stale members or we drop lazy scanning. >=20 > Comments, ideas? >=20 We don't need to see all disks to decide that there is no staleness. If you have an array with N devices and you can lose at most K of them, then you can check for staleness after you have seen max(K+1, N-K) drives. Why? Let those disks have generation numbers g_0,...,g_{N-1}. Our goal is to find the largest number G s.t. number of indices with g_i >=3D G is at least N-K. In most common case when you have seen K+1 disks all of them will have the same generation number g_0=3Dg_1=3D...=3Dg_{K} Then we know that G<=3Dg_0 Suppose not then all of 0,...,K are stale and we have lost K+1 drives which contradicts our goal. On the other hand when we have seen N-K devices we know that G>=3Dmin(g_0,...,g_{N-K-1}) as with G=3Dmin(g_0,...,g_{N-K-1}) we already have N-K disks. In cases other than mirror usually K+1<=3DN-K and so we don't even need t= o scan for more disks to detect staleness. The code will be slightly tricky as it has to handle tolerating staleness if there are too little disks but it's totally feasible. Let me figure out the rest of math and write a prototype. > _______________________________________________ > Grub-devel mailing list > Grub-devel@gnu.org > https://lists.gnu.org/mailman/listinfo/grub-devel >=20 --2rmMWNbbv6HHU24Ab7aKdMrEfrrlehGxU Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iF4EAREKAAYFAlWmoQQACgkQmBXlbbo5nOvMqgEAlqTj/bZsLxbk2bfiznXR5JiZ sPqUDZmoU2EGoT1UFnwA/AwDn+tgVuaDia4y7SaOcxfk5SRD/sSUWV19TLAJGazv =8v1p -----END PGP SIGNATURE----- --2rmMWNbbv6HHU24Ab7aKdMrEfrrlehGxU--