From owner-freebsd-bugs@FreeBSD.ORG Sat Oct 28 19:50:29 2006 Return-Path: X-Original-To: freebsd-bugs@hub.freebsd.org Delivered-To: freebsd-bugs@hub.freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 3F97816A523 for ; Sat, 28 Oct 2006 19:50:29 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [216.136.204.21]) by mx1.FreeBSD.org (Postfix) with ESMTP id EDB0643D5D for ; Sat, 28 Oct 2006 19:50:28 +0000 (GMT) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (gnats@localhost [127.0.0.1]) by freefall.freebsd.org (8.13.4/8.13.4) with ESMTP id k9SJoSsg076295 for ; Sat, 28 Oct 2006 19:50:28 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.13.4/8.13.4/Submit) id k9SJoSho076294; Sat, 28 Oct 2006 19:50:28 GMT (envelope-from gnats) Date: Sat, 28 Oct 2006 19:50:28 GMT Message-Id: <200610281950.k9SJoSho076294@freefall.freebsd.org> To: freebsd-bugs@FreeBSD.org From: Bruce Evans Cc: Subject: Re: bin/104458: fts(3) can't handle very deep trees X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: Bruce Evans List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 28 Oct 2006 19:50:29 -0000 The following reply was made to PR bin/104458; it has been noted by GNATS. From: Bruce Evans To: Yar Tikhiy Cc: Subject: Re: bin/104458: fts(3) can't handle very deep trees Date: Mon, 16 Oct 2006 22:53:40 +1000 (EST) >> Description: > > Utilities using fts(3), find(1) and rm(1) being among them, > fail to handle a directory tree so deep that a path in it is > longer than ~49-50K. ISTR that POSIX requires at least rm and cp to work with any depth that can occur in theory, and QOI of course requires any utility that traverses trees to work with any possiible depth that occurs in practice. cp ensures brokeness using FTS_NOCHDIR, but this bug is missing in cp. This was easy to debug. fts has a bogus USHRT_MAX limit on path lengths in FTSENT. It normally fails at about 50K because it keeps doubling the length and 2*50K is the first doubling to above 64K. FTS only has a limit of INT_MAX. These limits are well documented in the source. >> How-To-Repeat: > > 1. Create a long chain of subdirectories using the script > attached. Each subdir name will be "000...". The overall > structure will be 000*/000*/000*/000*/... > This is better done on a scratch mfs because the > resulting chain will be hard to delete using stock tools. I used /compat/linux/bin/cp. It just worked :-(. /compat/linux/usr/bin/du also just worked, while du just failed. I debugged using du. FTSENT has quite a few shorts. ISTR a discussion about one of them not being large enough for use as a cookie, but don't remember the path length one being noticed as a limit before. It also has a limit of 64K on the number of levels. This can easily be reached. It also has some INT_MAX limits. These are not easy to reach yet. Implementing the POSIX requirement to work for any tree is an interesting problem. The program cannot use any stacks or counters, since no stack or counter can be large enough. However, a counter with 640K of bits should be large enough for anyone in practice. A stack of parent directories can easily overflow in practice. In particular, ".." must be used to traverse back since a stack of fd's to fchdir() back to would hit the {OPEN_MAX} limit very easily. fts(3) seems to handle this right (it doesn't keep directories open). ft's most fundamental limit seems to be the INT_MAX one on path lengths. For some reason, it wants to construct a full path. That feature should probably just be turned off for deep paths, or always as an option, since it is impossible to use paths longer than {PATH_MAX} and often only the path relative to a subdir is needed/ Bruce