From owner-freebsd-standards@freebsd.org Thu Apr 13 02:59:27 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 79C7BD385CA for ; Thu, 13 Apr 2017 02:59:27 +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 5E46AAD3 for ; Thu, 13 Apr 2017 02:59:27 +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 v3D2xRdp054426 for ; Thu, 13 Apr 2017 02:59:27 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: Thu, 13 Apr 2017 02:59:27 +0000 X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: new 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: ash@ixsystems.com 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: bug_id short_desc product version rep_platform op_sys bug_status bug_severity priority component assigned_to reporter Message-ID: 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: Thu, 13 Apr 2017 02:59:27 -0000 https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D218622 Bug ID: 218622 Summary: libc/gen/telldir [hack-n-PATCH] performance limited to O(n) vs file count, O(n^2) against samba ls workload Product: Base System Version: 11.0-STABLE Hardware: Any OS: Any Status: New Severity: Affects Many People Priority: --- Component: standards Assignee: freebsd-standards@FreeBSD.org Reporter: ash@ixsystems.com We have been tracking a performance regression in FreeBSD 11 stable based s= mbd pegs a cpu and takes much longer to list huge directories than it's FreeBSD= 9.x base counterpart . Profiling showed that the time was geometrically relate= d to file count within the directory.=20 Samba emits a telldir for every file during a readdir; and in 9.x that seem= ed to run in linear time and things where fine; however this change appears to expands the workload of list scan to O(n^2) vs file count.=20 https://svnweb.freebsd.org/base/stable/11/lib/libc/gen/telldir.c?r1=3D23564= 7&r2=3D269204 For a directory with 64k files, the performance is as follows when driven by samba listing files. Identical hardware and zfs data sets are used: using dtrace script: BEGIN { printf("thinking, hit control-c when you are tired of it");} pid$1::$2:entry { self->st=3D timestamp; } pid$1::$2:return { @[execname,"delta(ns)" ] =3D quantize( timestamp - self->st); self->st =3D 0; } 9.3:=20 #./dt_time_in_pid_func.dt `top -b | head -10 | tail -1 | chomp | cut -w -f1` telldir=20 dtrace: script './dt_time_in_pid_func.dt' matched 3 probes CPU ID FUNCTION:NAME 7 1 :BEGIN thinking, hit control-c when you are tired of it ^C smbd delta(ns)=20=20=20=20= =20=20=20=20=20=20=20=20=20=20=20=20=20 value ------------- Distribution ------------- count=20=20=20=20 2048 | 0=20=20=20=20=20= =20=20=20 4096 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 53883=20=20=20=20 8192 |@ 730=20=20=20=20= =20=20 16384 | 502=20=20=20=20= =20 and under 11-stable(ish): #dtrace -s dtprofile.is_in_path.dt `top -b | head -10 | tail -1 | chomp | = cut -w -f1` telldir=20=20 dtrace: script 'dtprofile.is_in_path.dt' matched 2 probes ^C deltans=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20 value ------------- Distribution ------------- count=20=20=20=20 2048 | 0=20=20=20=20=20= =20=20=20 4096 | 90=20=20=20=20= =20=20=20 8192 | 8=20=20=20=20=20= =20=20=20 16384 | 0=20=20=20=20=20= =20=20=20 32768 | 0=20=20=20=20=20= =20=20=20 65536 |@ 1583=20=20=20=20= =20 131072 |@@@@@@@@@@ 12270=20=20=20=20 262144 |@@@@@@@@@@@@@@@@@@@@@@ 28159 <<- libc telldir takes how long now?! 524288 |@@@@@@@ 9299=20=20=20=20= =20 1048576 |=20=20=20=20=20=20 After reverting the telldir change shamelessly: https://github.com/freenas/os/commit/92873f3190c830302143d759411b23bd719b0b= a2 Performance for the telldir returned to constant time.=20 The change appears important to @standards however the impact is tough to explain to samba users. To conjecture, I wonder if a run time tunable could select the 'conforming' or 'fast' behaviour for telldir like LD_PRELOAD... style directives. --=20 You are receiving this mail because: You are the assignee for the bug.=