From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk0-f194.google.com ([209.85.220.194]:35749 "EHLO mail-qk0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753717AbdG2OYj (ORCPT ); Sat, 29 Jul 2017 10:24:39 -0400 Received: by mail-qk0-f194.google.com with SMTP id a77so5985861qkb.2 for ; Sat, 29 Jul 2017 07:24:39 -0700 (PDT) To: linux-fsdevel , jack@suse.com From: Sean Anderson Subject: [ext2] Mislabeled quadratic probing? Message-ID: <07c8955b-0ead-9dd9-978e-767d5dec6712@gmail.com> Date: Sat, 29 Jul 2017 10:24:29 -0400 MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="36cw7JgIbJEjDvtCoEuw94XHeThot7tVj" Sender: linux-fsdevel-owner@vger.kernel.org List-ID: This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --36cw7JgIbJEjDvtCoEuw94XHeThot7tVj Content-Type: multipart/mixed; boundary="InlgpauGos9ldUbISPlWgbIkIbTDkbsxq"; protected-headers="v1" From: Sean Anderson To: linux-fsdevel , jack@suse.com Message-ID: <07c8955b-0ead-9dd9-978e-767d5dec6712@gmail.com> Subject: [ext2] Mislabeled quadratic probing? --InlgpauGos9ldUbISPlWgbIkIbTDkbsxq Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: quoted-printable Hi, I was reading through the ext2 inode allocation code, and found the following snippet in fs/ext2/ialloc.c:find_group_other /* * Use a quadratic hash to find a group with a free inode and some * free blocks. */ for (i =3D 1; i < ngroups; i <<=3D 1) { group +=3D i; if (group >=3D ngroups) group -=3D ngroups; desc =3D ext2_get_group_desc (sb, group, NULL); if (desc && le16_to_cpu(desc->bg_free_inodes_count) && le16_to_cpu(desc->bg_free_blocks_count)) goto found; } As I understand it, quadratic probing starting at a hash H would try positions H+1, H+4, H+9, H+16, H+25, etc. Here, however, the algorithm appears to try positions H+1, H+3, H+7, H+15, H+31, etc., which appears to be some form of exponential probing. I was unable to find the patch which introduced this code, but it appears that it was introduced in v2.4.14.3, and before that linear probing was used. Clearly, this code works, and I can't really find any compelling arguments to switch to quadratic probing proper. I suspect it was done this way to avoid a multiply or an extra subtract on every loop. Can anyone shed some light on the choice (and apparent mislabel) of this algorithm? --Sean --InlgpauGos9ldUbISPlWgbIkIbTDkbsxq-- --36cw7JgIbJEjDvtCoEuw94XHeThot7tVj Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- iQGTBAEBCgB9FiEEkGEdW86NSNID6GAoPuiP7LShEG4FAll8mp1fFIAAAAAALgAo aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDkw NjExRDVCQ0U4RDQ4RDIwM0U4NjAyODNFRTg4RkVDQjRBMTEwNkUACgkQPuiP7LSh EG7Qlwf8CglNOuiwoOFTBq2VS8YMfOw2j9MVmIWt7DZHDreghKo2XtgwWPjCe2UG afdU9YoHwxh3qlPtbJxJAPDlCKk0t28zcmIFXzOaY2SzkS1+oUvJkQ3dXJlpYww5 Tv0y2ivJgEUYo8/92KQ6Qr/ABxyPYx51wm3fA5A7MOt4ote7KH4MdhFuuCnLxe5u FWxE1CKDucXpMzmtp4gFMGjN8aMKbwafPANLT/xMATut/v/lBhX5d+cMAkap9nZc qNLQjb+CgLnCUViUX8D5uyK3VKJqyzp5oMK/otcGYXYYCTbNaKbpW6zcoUypS+ZJ NiFNXNfM/h3Jh6PsqzcVuPIpuwOskA== =dl7a -----END PGP SIGNATURE----- --36cw7JgIbJEjDvtCoEuw94XHeThot7tVj--