Date: Thu, 13 Apr 2017 02:59:27 +0000 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 Message-ID: <bug-218622-15@https.bugs.freebsd.org/bugzilla/>
next in thread | raw e-mail | index | archive | help
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.=
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?bug-218622-15>