From owner-freebsd-standards@freebsd.org Fri Apr 14 17:37:36 2017 Return-Path: Delivered-To: freebsd-standards@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id BC957D3E80C for ; Fri, 14 Apr 2017 17:37:36 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from kenobi.freebsd.org (kenobi.freebsd.org [IPv6:2001:1900:2254:206a::16:76]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id AB98DD92 for ; Fri, 14 Apr 2017 17:37:36 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from bugs.freebsd.org ([127.0.1.118]) by kenobi.freebsd.org (8.15.2/8.15.2) with ESMTP id v3EHbakQ077417 for ; Fri, 14 Apr 2017 17:37:36 GMT (envelope-from bugzilla-noreply@freebsd.org) From: bugzilla-noreply@freebsd.org To: freebsd-standards@FreeBSD.org Subject: [Bug 218622] libc/gen/telldir [hack-n-PATCH] performance limited to O(n) vs file count, O(n^2) against samba ls workload Date: Fri, 14 Apr 2017 17:37:36 +0000 X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: Base System X-Bugzilla-Component: standards X-Bugzilla-Version: 11.0-STABLE X-Bugzilla-Keywords: X-Bugzilla-Severity: Affects Many People X-Bugzilla-Who: jhb@FreeBSD.org X-Bugzilla-Status: New X-Bugzilla-Resolution: X-Bugzilla-Priority: --- X-Bugzilla-Assigned-To: freebsd-standards@FreeBSD.org X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: https://bugs.freebsd.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: freebsd-standards@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Standards compliance List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 14 Apr 2017 17:37:36 -0000 https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D218622 --- Comment #2 from John Baldwin --- So this wasn't purely about standards@ compliance, but there was actual software that was broken on FreeBSD because of this (it might have involved using telldir() on a large directory accessed via NFS where the client brok= e.=20 If it's the thing I'm thinking of then you would have an 'ls' on a large NFS directory that would never complete). The larger fix is to change getdirentries() to report a valid seek location with each 'struct dirent'.= =20 That depends on changing the contents of 'struct dirent' which is a non-tri= vial thing to do, but is included in the ongoing 'ino64' work. Once that is in place you don't need the telldir cookies at all. One thing you could do for now is replace the linear O(n) search with something better like a tree that you can do a binary search on. --=20 You are receiving this mail because: You are the assignee for the bug.=