From mboxrd@z Thu Jan 1 00:00:00 1970 From: ludo@gnu.org (Ludovic =?UTF-8?Q?Court=C3=A8s?=) Subject: bug#24937: "deleting unused links" GC phase is too slow Date: Sun, 11 Dec 2016 14:46:13 +0100 Message-ID: <87lgvm4lzu.fsf@gnu.org> References: <87wpg7ffbm.fsf@gnu.org> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Return-path: Received: from eggs.gnu.org ([2001:4830:134:3::10]:44073) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cG4Wv-0002Wc-4W for bug-guix@gnu.org; Sun, 11 Dec 2016 08:51:09 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cG4Ws-0006NV-18 for bug-guix@gnu.org; Sun, 11 Dec 2016 08:51:05 -0500 Received: from debbugs.gnu.org ([208.118.235.43]:50488) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cG4Wr-0006NF-U9 for bug-guix@gnu.org; Sun, 11 Dec 2016 08:51:01 -0500 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1cG4Wr-0003c9-JK for bug-guix@gnu.org; Sun, 11 Dec 2016 08:51:01 -0500 In-Reply-To: <87wpg7ffbm.fsf@gnu.org> Sender: "Debbugs-submit" Resent-Message-ID: List-Id: Bug reports for GNU Guix List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guix-bounces+gcggb-bug-guix=m.gmane.org@gnu.org Sender: "bug-Guix" To: 24937@debbugs.gnu.org --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Hello! Here=E2=80=99s a proposed patch that follows your suggestion, Mark, but pla= ces an upper bound on the number of directory entries loaded in memory. On my laptop, which has ~500k entries in /gnu/store/.links, the result is something like this (notice the inode numbers in =E2=80=98lstat=E2=80=99= calls): --8<---------------cut here---------------start------------->8--- 13738 write(4, "gmlo\0\0\0\0\31\0\0\0\0\0\0\0deleting unused "..., 48) =3D = 48 13738 open("/gnu/store/.links", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) = =3D 8 13738 fstat(8, {st_dev=3Dmakedev(8, 2), st_ino=3D4014083, st_mode=3DS_IFDIR= |0755, st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks= =3D119224, st_size=3D60977152, st_atime=3D2016/12/11-12:01:59, st_mtime=3D2= 016/12/11-09:39:45, st_ctime=3D2016/12/11-09:39:45}) =3D 0 13738 getdents(8, {{d_ino=3D4014083, d_off=3D4294967296, d_reclen=3D24, d_n= ame=3D"."} [...] 13738 lstat("/gnu/store/.links/1f2f3g8waxwymp9sl2slcfyara164i8w1y2sz3h9js2f= cviv2rnc", {st_dev=3Dmakedev(8, 2), st_ino=3D47, st_mode=3DS_IFREG|0444, st= _nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D88, st_s= ize=3D41482, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:01= , st_ctime=3D2015/11/25-11:29:20}) =3D 0 13738 lstat("/gnu/store/.links/1p25kpyfw354in4kykmgh5sy9h925hnil1jdzgxhz7n6= abbws8px", {st_dev=3Dmakedev(8, 2), st_ino=3D65, st_mode=3DS_IFREG|0444, st= _nlink=3D9, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_si= ze=3D2313, st_atime=3D2016/12/08-21:02:26, st_mtime=3D1970/01/01-01:00:01, = st_ctime=3D2016/12/11-01:44:49}) =3D 0 13738 lstat("/gnu/store/.links/163187g637br9ys5pmshb01wjav53bs1g1a83m7c2alp= dyx3yqz2", {st_dev=3Dmakedev(8, 2), st_ino=3D68, st_mode=3DS_IFREG|0444, st= _nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D32, st_s= ize=3D13561, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:01= , st_ctime=3D2015/11/25-11:29:20}) =3D 0 [...] 13738 getdents(8, {{d_ino=3D4257114, d_off=3D1734093409898198492, [...] 13738 lstat("/gnu/store/.links/1m6g06i01ybbkhjjbirjnj7fckw1b772cwygkvbd6v6z= gkln7f7m", {st_dev=3Dmakedev(8, 2), st_ino=3D19, st_mode=3DS_IFREG|0444, st= _nlink=3D4, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_si= ze=3D2553, st_atime=3D2016/12/08-21:02:54, st_mtime=3D1970/01/01-01:00:01, = st_ctime=3D2016/12/07-00:05:19}) =3D 0 13738 lstat("/gnu/store/.links/1ml8n3q55ikn8h60sn67jq1y7z7mvdp5kwr33pqrid2r= 6kk1d4kb", {st_dev=3Dmakedev(8, 2), st_ino=3D30, st_mode=3DS_IFREG|0444, st= _nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_si= ze=3D2090, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:01, = st_ctime=3D2015/11/25-11:29:21}) =3D 0 13738 lstat("/gnu/store/.links/1c8cvwlqyyqby3k13cwm40g26pwca5iiz5dcj43xrgn9= y91lfvc2", {st_dev=3Dmakedev(8, 2), st_ino=3D33, st_mode=3DS_IFREG|0444, st= _nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D16, st_s= ize=3D7958, st_atime=3D2015/11/04-18:55:32, st_mtime=3D1970/01/01-01:00:01,= st_ctime=3D2016/01/05-11:35:49}) =3D 0 [...] 13738 getdents(8, {{d_ino=3D328672, [...] 13738 lstat("/gnu/store/.links/1l55l59dxb74himmkfzx5v63cv7287i6rjhdns1fdlwa= jqd73lnz", {st_dev=3Dmakedev(8, 2), st_ino=3D21, st_mode=3DS_IFREG|0444, st= _nlink=3D31, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_s= ize=3D615, st_atime=3D2016/12/08-21:02:30, st_mtime=3D1970/01/01-01:00:01, = st_ctime=3D2016/12/11-01:44:47}) =3D 0 13738 lstat("/gnu/store/.links/1c7mm5amw743mb45f1zg4d4r3g549ch35wks9izkcgkx= 0jirpxsg", {st_dev=3Dmakedev(8, 2), st_ino=3D48, st_mode=3DS_IFREG|0444, st= _nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D360, st_= size=3D176750, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:= 01, st_ctime=3D2015/11/25-11:29:20}) =3D 0 13738 lstat("/gnu/store/.links/0z5s7b0yk8mfn1np6gk3cdbmpnjgxg1g0l8vfq1aa01z= wp06d3f0", {st_dev=3Dmakedev(8, 2), st_ino=3D61, st_mode=3DS_IFREG|0444, st= _nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_si= ze=3D1440, st_atime=3D2016/11/03-20:37:50, st_mtime=3D1970/01/01-01:00:01, = st_ctime=3D2016/11/07-00:01:57}) =3D 0 --8<---------------cut here---------------end--------------->8--- I can=E2=80=99t tell exactly how this affects performance because my machin= e has an SSD where this operation takes ~3 seconds on a cold cache. I suspect it has performance comparable to that of doing all the =E2=80=98readdir=E2= =80=99 at once followed by all the =E2=80=98lstat=E2=80=99. Mark, how does that sound? I=E2=80=99d like to commit it soon if there are no objections. Thanks, Ludo=E2=80=99. --=-=-= Content-Type: text/x-patch Content-Disposition: inline diff --git a/nix/libstore/gc.cc b/nix/libstore/gc.cc index 72eff52..db58603 100644 --- a/nix/libstore/gc.cc +++ b/nix/libstore/gc.cc @@ -545,6 +545,9 @@ void LocalStore::tryToDelete(GCState & state, const Path & path) } +/* Like 'dirent', but with just what we need. */ +typedef std::pair MiniDirEntry; + /* Unlink all files in /nix/store/.links that have a link count of 1, which indicates that there are no other links and so they can be safely deleted. FIXME: race condition with optimisePath(): we @@ -555,32 +558,57 @@ void LocalStore::removeUnusedLinks(const GCState & state) AutoCloseDir dir = opendir(linksDir.c_str()); if (!dir) throw SysError(format("opening directory `%1%'") % linksDir); + /* Maximum number of entries stored in memory; each 'MiniDirEntry' takes + ~80 bytes. */ + const size_t maxEntries = 100000; + long long actualSize = 0, unsharedSize = 0; - struct dirent * dirent; - while (errno = 0, dirent = readdir(dir)) { - checkInterrupt(); - string name = dirent->d_name; - if (name == "." || name == "..") continue; - Path path = linksDir + "/" + name; - - struct stat st; - if (lstat(path.c_str(), &st) == -1) - throw SysError(format("statting `%1%'") % path); - - if (st.st_nlink != 1) { - unsigned long long size = st.st_blocks * 512ULL; - actualSize += size; - unsharedSize += (st.st_nlink - 1) * size; - continue; - } - - printMsg(lvlTalkative, format("deleting unused link `%1%'") % path); - - if (unlink(path.c_str()) == -1) - throw SysError(format("deleting `%1%'") % path); - - state.results.bytesFreed += st.st_blocks * 512; + bool endOfDir = false; + + while (!endOfDir) { + /* Read as many entries as possible at once, up to 'maxEntries'. */ + std::list entries; + struct dirent * dirent; + while (errno = 0, + (entries.size() < maxEntries) && (dirent = readdir(dir))) { + checkInterrupt(); + string name = dirent->d_name; + if (name == "." || name == "..") continue; + entries.emplace_back(MiniDirEntry(name, dirent->d_ino)); + } + + endOfDir = (dirent == NULL); + + /* Sort entries by inode number to minimize disk seeks induced by the + following 'lstat' calls. */ + entries.sort([] (const MiniDirEntry& e1, const MiniDirEntry& e2) { + return e1.second < e2.second; + }); + + for (auto && item: entries) { + checkInterrupt(); + + Path path = linksDir + "/" + item.first; + + struct stat st; + if (lstat(path.c_str(), &st) == -1) + throw SysError(format("statting `%1%'") % path); + + if (st.st_nlink != 1) { + unsigned long long size = st.st_blocks * 512ULL; + actualSize += size; + unsharedSize += (st.st_nlink - 1) * size; + continue; + } + x+ printMsg(lvlTalkative, format("deleting unused link `%1%'") % path); + + if (unlink(path.c_str()) == -1) + throw SysError(format("deleting `%1%'") % path); + + state.results.bytesFreed += st.st_blocks * 512; + } } struct stat st; --=-=-=--