From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/10311 Path: news.gmane.org!not-for-mail From: Joakim Sindholt Newsgroups: gmane.linux.lib.musl.general Subject: Re: nftw miscalculates FTW.base when pathnames end in / Date: Tue, 12 Jul 2016 11:41:40 +0200 Message-ID: <1468316500.14738.1@mail.zhasha.com> References: <1462369339.29574.1@mail.zhasha.com> <20160514030109.GN21636@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-O10JSS0xK31DBL5PpXOl" X-Trace: ger.gmane.org 1468316540 10407 80.91.229.3 (12 Jul 2016 09:42:20 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 12 Jul 2016 09:42:20 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-10324-gllmg-musl=m.gmane.org@lists.openwall.com Tue Jul 12 11:42:06 2016 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1bMuCQ-0004Yj-DO for gllmg-musl@m.gmane.org; Tue, 12 Jul 2016 11:41:54 +0200 Original-Received: (qmail 22442 invoked by uid 550); 12 Jul 2016 09:41:52 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 22424 invoked from network); 12 Jul 2016 09:41:51 -0000 In-Reply-To: <20160514030109.GN21636@brightrain.aerifal.cx> X-Mailer: geary/0.11.0 Xref: news.gmane.org gmane.linux.lib.musl.general:10311 Archived-At: --=-O10JSS0xK31DBL5PpXOl Content-Type: text/plain; charset=utf-8; format=flowed On Sat, May 14, 2016 at 5:01 AM, Rich Felker wrote: > lev.base is computed separately depending on whether or not there's a > previous history; for the no-history case, it should be computed by > skipping all trailing slashes, then backing up until the previous > slash or beginning of string, whichever is hit first. But rather than > special-casing !h in do_nftw, the top-level nftw function should > probably set up a fake "-1 level" history structure to pass in. This > gathers the special top-level logic all in one place. I had a look at copying the entire path over and adjusting the first .base accordingly. The problem then became that the root dir would come out as being named something////// depending on how many slashed I added. This runs counter to the glibc behavior which also just hacks off the slashes. In the end I think it's cleaner to just remove trailing slashes than to have them included in all but the root dir. As per your recommendation I also set up a fake -1 history level and removed the special casing for !h, but I'm unsure what default values should be used for dev and ino. Then, as we talked about on IRC, I tried to reduce the stack usage of do_nftw, which was 296 B when all was said and done. By moving a lot of the context stuff explicitly into nftw it got all the way down to 88 on clang and 104 on gcc. Depending on a few minor details those two numbers would switch around. I'm not sure why. In any case it's a third of what it was and I would consider that a substantial win. The code isn't exactly beautiful though. --=-O10JSS0xK31DBL5PpXOl Content-Type: multipart/mixed; boundary="=-+URKRV0dbg+tXAb3ujbS" --=-+URKRV0dbg+tXAb3ujbS Content-Type: text/x-patch Content-Disposition: attachment; filename=0002-optimize-nftw-for-stack-usage.patch >From 5244c0e3fec2af28bf3922b4f0e45b209880f27e Mon Sep 17 00:00:00 2001 From: Joakim Sindholt Date: Tue, 12 Jul 2016 11:12:24 +0200 Subject: [PATCH 2/2] optimize nftw for stack usage Before this we would see 296 bytes of stack used per frame on amd64 using clang, and after it's all the way down to 88 bytes per frame. Less than a third of what it was and much more reasonable. --- src/misc/nftw.c | 91 ++++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 58 insertions(+), 33 deletions(-) diff --git a/src/misc/nftw.c b/src/misc/nftw.c index 7df7226..6057d89 100644 --- a/src/misc/nftw.c +++ b/src/misc/nftw.c @@ -8,6 +8,18 @@ #include #include "libc.h" +struct context +{ + char *path; + int (*fn)(const char *, const struct stat *, int, struct FTW *); + int fd_limit; + int flags; + + size_t l; + struct stat st; + struct FTW lev; +}; + struct history { struct history *chain; @@ -20,68 +32,70 @@ struct history #undef dirfd #define dirfd(d) (*(int *)d) -static int do_nftw(char *path, int (*fn)(const char *, const struct stat *, int, struct FTW *), int fd_limit, int flags, struct history *h) +static int do_nftw(struct context *c, struct history *h) { - size_t l = strlen(path), j = l && path[l-1]=='/' ? l-1 : l; - struct stat st; struct history new; int type; int r; - struct FTW lev; - char *name; - if ((flags & FTW_PHYS) ? lstat(path, &st) : stat(path, &st) < 0) { - if (!(flags & FTW_PHYS) && errno==ENOENT && !lstat(path, &st)) + if ((c->flags & FTW_PHYS) ? lstat(c->path, &c->st) : stat(c->path, &c->st) < 0) { + if (!(c->flags & FTW_PHYS) && errno==ENOENT && !lstat(c->path, &c->st)) type = FTW_SLN; else if (errno != EACCES) return -1; else type = FTW_NS; - } else if (S_ISDIR(st.st_mode)) { - if (access(path, R_OK) < 0) type = FTW_DNR; - else if (flags & FTW_DEPTH) type = FTW_DP; + } else if (S_ISDIR(c->st.st_mode)) { + if (access(c->path, R_OK) < 0) type = FTW_DNR; + else if (c->flags & FTW_DEPTH) type = FTW_DP; else type = FTW_D; - } else if (S_ISLNK(st.st_mode)) { - if (flags & FTW_PHYS) type = FTW_SL; + } else if (S_ISLNK(c->st.st_mode)) { + if (c->flags & FTW_PHYS) type = FTW_SL; else type = FTW_SLN; } else { type = FTW_F; } - if ((flags & FTW_MOUNT) && st.st_dev != h->dev) + if ((c->flags & FTW_MOUNT) && c->st.st_dev != h->dev) return 0; - + new.chain = h; - new.dev = st.st_dev; - new.ino = st.st_ino; + new.dev = c->st.st_dev; + new.ino = c->st.st_ino; new.level = h->level+1; - new.base = j+1; + new.base = c->l+1; - lev.level = new.level; - lev.base = h->base; - - if (!(flags & FTW_DEPTH) && (r=fn(path, &st, type, &lev))) - return r; + if (!(c->flags & FTW_DEPTH)) { + c->lev.level = new.level; + c->lev.base = h->base; + if ((r=c->fn(c->path, &c->st, type, &c->lev))) + return r; + } for (; h; h = h->chain) - if (h->dev == st.st_dev && h->ino == st.st_ino) + if (h->dev == c->st.st_dev && h->ino == c->st.st_ino) return 0; - if ((type == FTW_D || type == FTW_DP) && fd_limit) { - DIR *d = opendir(path); + if ((type == FTW_D || type == FTW_DP) && c->fd_limit) { + DIR *d = opendir(c->path); if (d) { struct dirent *de; while ((de = readdir(d))) { + size_t dl; if (de->d_name[0] == '.' && (!de->d_name[1] || (de->d_name[1]=='.' && !de->d_name[2]))) continue; - if (strlen(de->d_name) >= PATH_MAX-l) { + if ((dl=strlen(de->d_name)) > PATH_MAX-new.base) { errno = ENAMETOOLONG; closedir(d); return -1; } - path[j]='/'; - strcpy(path+j+1, de->d_name); - if ((r=do_nftw(path, fn, fd_limit-1, flags, &new))) { + c->l = new.base+dl; + c->path[new.base-1]='/'; + memcpy(c->path+new.base, de->d_name, dl+1); + --c->fd_limit; + r=do_nftw(c, &new); + ++c->fd_limit; + if (r) { closedir(d); return r; } @@ -91,16 +105,21 @@ static int do_nftw(char *path, int (*fn)(const char *, const struct stat *, int, return -1; } } + c->path[new.base-1]=0; - path[l] = 0; - if ((flags & FTW_DEPTH) && (r=fn(path, &st, type, &lev))) - return r; + if (c->flags & FTW_DEPTH) { + c->lev.level = new.level; + c->lev.base = h->base; + if ((r=c->fn(c->path, &c->st, type, &c->lev))) + return r; + } return 0; } int nftw(const char *path, int (*fn)(const char *, const struct stat *, int, struct FTW *), int fd_limit, int flags) { + struct context c; struct history h; int r, cs; size_t l; @@ -126,8 +145,14 @@ int nftw(const char *path, int (*fn)(const char *, const struct stat *, int, str while (h.base && pathbuf[h.base-1]!='/') --h.base; + c.path = pathbuf; + c.fn = fn; + c.fd_limit = fd_limit; + c.flags = flags; + c.l = l; + pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cs); - r = do_nftw(pathbuf, fn, fd_limit, flags, &h); + r = do_nftw(&c, &h); pthread_setcancelstate(cs, 0); return r; } -- 2.7.3 --=-+URKRV0dbg+tXAb3ujbS Content-Type: text/x-patch Content-Disposition: attachment; filename=0001-ignore-trailing-slashes-in-nftw-path.patch >From 9896c027a6b261e09dff68d61993bb60313e9166 Mon Sep 17 00:00:00 2001 From: Joakim Sindholt Date: Tue, 12 Jul 2016 10:14:34 +0200 Subject: [PATCH 1/2] ignore trailing slashes in nftw path --- src/misc/nftw.c | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) diff --git a/src/misc/nftw.c b/src/misc/nftw.c index efb2b89..7df7226 100644 --- a/src/misc/nftw.c +++ b/src/misc/nftw.c @@ -46,17 +46,17 @@ static int do_nftw(char *path, int (*fn)(const char *, const struct stat *, int, type = FTW_F; } - if ((flags & FTW_MOUNT) && h && st.st_dev != h->dev) + if ((flags & FTW_MOUNT) && st.st_dev != h->dev) return 0; new.chain = h; new.dev = st.st_dev; new.ino = st.st_ino; - new.level = h ? h->level+1 : 0; - new.base = l+1; + new.level = h->level+1; + new.base = j+1; lev.level = new.level; - lev.base = h ? h->base : (name=strrchr(path, '/')) ? name-path : 0; + lev.base = h->base; if (!(flags & FTW_DEPTH) && (r=fn(path, &st, type, &lev))) return r; @@ -101,6 +101,7 @@ static int do_nftw(char *path, int (*fn)(const char *, const struct stat *, int, int nftw(const char *path, int (*fn)(const char *, const struct stat *, int, struct FTW *), int fd_limit, int flags) { + struct history h; int r, cs; size_t l; char pathbuf[PATH_MAX+1]; @@ -108,14 +109,25 @@ int nftw(const char *path, int (*fn)(const char *, const struct stat *, int, str if (fd_limit <= 0) return 0; l = strlen(path); + while (l && path[l-1]=='/') + --l; if (l > PATH_MAX) { errno = ENAMETOOLONG; return -1; } - memcpy(pathbuf, path, l+1); + memcpy(pathbuf, path, l); + pathbuf[l] = 0; + h.chain = NULL; + h.dev = (dev_t)-1; + h.ino = (ino_t)-1; + h.level = -1; + h.base = l; + while (h.base && pathbuf[h.base-1]!='/') + --h.base; + pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cs); - r = do_nftw(pathbuf, fn, fd_limit, flags, NULL); + r = do_nftw(pathbuf, fn, fd_limit, flags, &h); pthread_setcancelstate(cs, 0); return r; } -- 2.7.3 --=-+URKRV0dbg+tXAb3ujbS-- --=-O10JSS0xK31DBL5PpXOl--