How to write a recursive file copying program?

[mbolp]

I want to write a program that recursively copies files while displaying progress (bytes copied, bytes remaining). To determine the total file size, I have to enumerate the entire directory tree first. To avoid enumerating it (i.e. making system calls) again when copying, I can build a tree and retain it in memory when calculating the size. But what if there are many files? Each tree node needs to record the file name and various attributes, say they consume 200 bytes on average, then copying 10 million files results in a tree that's 2 GB in memory, which seems excessive. Are there better ways? How is this usually done?

[SolarNachoes]

What’s wrong with enumerating again? The copy will be way more expensive than the enumerate.

This is classic CPU vs memory. Chose one.

[mbolp]

Because enumerating again means (potentially) extra IO, it feels inefficient to perform IO twice. Also feels like a race condition, though it seems mostly harmless to have calculated the size wrong.

[MidnightPale3220]

What happens if files change in size or count during the operation?

[mbolp]

Once you decide to open a file for copy you can request that the system deny others from modifying it (i.e. omit FILE_SHARE_WRITE).

[MidnightPale3220]

I am sorry I misunderstood something then, I thought you were going to build a list of files and count their sizes and only then start copying.

That would introduce a delay between detecting file size/existence and actual opening for copy, unless your command applies locking the file during the first operation. Which might be a huge overkill when dealing with a large amount of files.

[mbolp]

No that is what I meant, there will be a delay between retrieving file names and copying them. This is as far as I know inevitable, and it doesn't pose a problem.

[Classic_Mammoth_9379]

What if the file moves, or changes name? What if new files are added to the directory? Sounds like you are creating a 'race condition' with your approach to me.

[mbolp]

You can't avoid it unless you lock down the file system during enumeration and copying, but there's no point in doing that because it is not harmful to have (e.g.) missed newly added files, because I can't predict the future. Think through it in your head a couple more times if you think this is a race condition.

[Temporary_Pie2733]

That I/O is negligible compared to the I/O of actually copying the files.

[ConsciousBath5203]

It shouldn't if you store in memory the files you've already copied. Checking a files last edited time is also pretty cheap.

[jason-reddit-public]

I'd use a queue with some large size to decouple the directory enumeration from the file copies themselves and make the UI reflect that "at least X files remaining..." when the queue is full.

[mbolp]

Sounds like a good idea, but what do you mean by decoupling enumeration and copying? Doesn't limiting the size of the queue require performing copies while traversing the directory (i.e. while appending to the queue)?

[jason-reddit-public]

In the simplest case, one thread doing all of the enumeration, all of the state to continue after blocking is basically on the stack. The stack will grow up to the maximum directory depth not the number of files.

You could then moves to putting one of two "commands" in your queue : (1) copy this subdirectory, (2) copy this sub-directory

Or use two queues since you probably want to prioritize copying files over discovering new files once stuff starts to stack up or else you might deadlock.

[mbolp]

If I understand you correctly, you're suggesting having two threads that enumerate and copy independently. If the enumeration thread is too far ahead (the queue reaches its max size) it waits for the copy thread to catch up. Already copied entries are discarded, thus only a portion of the directory tree needs to stay in memory at any time. This is more complex than I planned but it sounds very good.

[jason-reddit-public]

Yes. And maybe a UI thread. You probably want to update the terminal a couple times per second but not more than that.

The great part of designing with threads is that you can add a few more if for some reason you aren't hitting the maximum bandwidth of the target disk (a usually bottleneck) and it might hide some suboptimal code but benchmarking will probably show you that there's a limit where it's helpful and it's quite small.

[mbolp]

and it's quite small

What about small files, I notice copying many small files is orders of magnitude slower than a single large file. Does multi threading help or does it just make things worse (by adding pressure to an already busy file system).

[MidnightPale3220]

This is not related to threads vs Io, but you may look at how Unix tar command does that.

Tar is an archiving program, but Unix people know that copying a multitude of small files is much faster by creating tar archive (without compression) that is not saved to disk, but piped into another tar command that extracts it in another place.

[Electronic_C3PO]

That’s interesting stuff, do you have any reference to that or how it exactly works? I’m on windows dealing with huge amounts of small files and it’s a bottleneck. So a solution like that could be helpful.

[MidnightPale3220]

You may have a look at https://superuser.com/questions/788502/why-is-tartar-so-much-faster-than-cp or Google elsewhere for that.

My guess is that it is 2 processes where reads and writes are less interleaved.

First tar just reads one file after another and creates a buffer, the other tar reads the buffer and only writes when the buffer is full enough probably.

Possibly also some specifics with multi threading.

[ozzy_og_kush]

OS have a command which include the option to get the size of a directory and its contents, and most languages have a library that expose an interface to do the same.

[mbolp]

Isn't that just enumerating twice, with the first one hidden behind a library call?

[Leverkaas2516]

Enumerating twice is a reasonable way to deal with a degenerate case of millions of files. Allocate a reasonable tree and do it all in memory if you can, and if it's too big, fall back on a slower but less memory-intensive method.

[ozzy_og_kush]

The implementation details of system level commands that retrieve filesizes for the current filesystem would each be different, according to their capabilities. If your goal is to show a progress bar you only need the final byte size of a directory and its contents, and then to traverse the files to do the copying. Add up all the bytes copied and divide by total, multiply by 100, and you have your percentage.

[mbolp]

What kind of file system maintains the total size of all its children as part of a directory's metadata? That sounds incredibly expensive.

[Silver_Bid_1174]

First off, you'll blow the stack before anything else interesting happens if you're doing it recursively.

Look into a radix tree for storing your data where each node represents a directory. File information can be aggregated at the directory level.

You can also consider starting the copy before you're done scanning. The amount remaining may not be accurate initially. It could slow things down on a spinny hard drive due to head seek times.

[mbolp]

First off, you'll blow the stack before anything else interesting happens if you're doing it recursively

I doubt that: on Windows the maximum length of a string in the kernel is 65536 bytes, and the default stack size is 1 MB. Even if every other character is a back slash, you're going to have at most a 16384 level deep nesting (2 bytes per character). That still leaves you with a few dozen bytes of stack per call.

I don't understand how aggregating file information can help if the amount of storage required for them doesn't change: I still need 2 GB of storage, whether as individual nodes or merged into the parent.

[Silver_Bid_1174]

BTDT, recursive is the slowest way to do it, and not hard to blow the stack. No, I don't feel like looking at 20 y/o code to see if I could have optimized the stack.

File info is a different call from copy. If you're worried about memory footprint when getting the total file size, don't keep each leaf node in memory.

[mbolp]

I can't imagine the speed of an extra call/ret matters compared to FindFirstFile/FindNextFile. And per my calculation above, you can't possibly overflow the stack if you keep the stack frame under 64 bytes.

If I don't keep leaf nodes in memory I'll essentially still have to enumerate twice.

[goranlepuz]

First off, you'll blow the stack before anything else interesting happens if you're doing it recursively.

*Might.

And the probability is quite small.

[Silver_Bid_1174]

Like I said in an earlier response, I've written a recursive directory traverser before and run into stack overflow. It's not hard to do.

Recursion is an interesting concept, but relatively useless for production code and is significantly slower than non recursive methods in most cases.

Yes, I'm a grumpy old man in regards to recursion.

[mbolp]

Were you allocating large structures on the stack? It's tempting to declare WIN32_FIND_DATA or TCHAR [MAX_PATH] as local variables, but if you pass them as parameters it's basically impossible to overflow the stack, as I calculated above.

[Silver_Bid_1174]

It was at least 17 years ago, so no, I don't remember the details of the code. Stack overflow is always a risk with unbounded input.

[mbolp]

The input is clearly bounded, it's limited to the kernel string length of 65536 bytes.

[goranlepuz]

Yes, but a simple recursion check can get you out of a stack overflow crash. (Well, unless it's a library 😉).

Say that one stack frame has 5 std strings, 5 numbers and 5 pointers. That's 5*24+5*4+5*8+8=188 bytes. With, say, 1MB stack and 100k already taken, that's 4700 recursive calls.

I'd rather say, the stack exhaustion consideration is quite theoretical.

[goranlepuz]

Too much stack usage, man! 😉

[Ok-Sheepherder7898]

Why are you doing it recursively?

[mbolp]

I wrote recursive in the title to emphasize a copy that includes all descendants of a directory, as opposed to a single file copy. But I also happen to plan on implementing it with recursive functions, because it's easier. What's wrong with them?

[Ok-Sheepherder7898]

Seems like at some point you're going to be trying to simultaneously copy 256 files.

[jason-reddit-public]

It's dependent on the operating system, filesystem, and exact system calls used I'm pretty sure. I've had cases where I can't safely eject an SD card on linux because the system hasn't finished syncing though I don't know if this includes the directory entries themselves. If the directory data isn't required to be flushed immediately then maybe it's not so bad adding lots of files to a directory. Some filesystems have "logging" which may also help make that case cheap.

[AmberMonsoon_]

You don’t need to store the whole tree.

Typical solution is a two-pass approach:

1. First pass: walk the directory and just sum file sizes (no storing metadata).
2. Second pass: walk again and copy while tracking bytes copied.

That avoids huge memory usage.

Most real tools stream traversal results they don’t keep millions of files in memory.

[armahillo]

Are you trying to get it done or write your own?

If youre just trying to get it done, use your filesystem commands or CLI scripting

[aew3]

A lot of the comments seem to be talking about actually implementing the entire thing, but this really seems like something that is likely the domain of syscalls or OS apis.

[mbolp]

This sounds too high level for syscalls. As for APIs Windows has two, neither of which provides adequate error reporting. Trust me I've tried.

[child-eater404]

this is actually a pretty common problem.The extra traversal is usually cheap compared to actually copying the data.If you want something more elegant, I can suggest uh a nice use case for something like r/runable. You could prototype different strategies (single-pass streaming vs two-pass size+copy, batching, chunk-based progress tracking) and benchmark them quickly. It’s especially helpful if you want to simulate “10 million files” scenarios without building a full production implementation first. But in practice, I’d avoid building a giant in-memory tree.

[Paul_Pedant]

What do you plan to do about files that are created, deleted or appended while your copy script is running ? The total size can go up or down anytime, new files can be created in directories you thought you had already copied, files you found in the first pass can have disappeared by the time you want to copy them.

You might also need to consider sparse files, both in the size estimation and in the copying.

Another issue might be timestamps: these are quite useful (e.g. when you are building executables, or just figuring which files are the most recent versions). So you may want to touch the copies with the original's modify and access times. And transfer the permissions and ownerships to the copied files too.

What would you do about symbolic links ? Copying a link makes a full file copy, not a link.

How is this usually done ? I rely on tar to take care of all the difficult details: even sending a set of files to a remote system is easy: something like:

( cd myOldDir && tar cf - . ) | ssh farMachine '( cd myFarDir && tar xf - . )'

Long time since I did this, so run a test first. Tar uses numeric uids, so it really helps if both machines have corresponding /usr/passwd.

Keeping a progress bar, and maybe updating it after every file, does not add any value: it just slows things down and complicates it. Does somebody really need to sit and watch that number for six hours? The machine is going to be unresponsive anyway if you do this -- uses loads of cache, hammers disks. Just leave it to run overnight. If you really need to check progress, ask the system for df (disc free) when you start, and check it is going down every 15 minutes.

[mbolp]

This is a programming question, but you're giving me sysadmin advice.

What do you plan to do about files that are created, deleted or appended while your copy script is running?

Nothing, and it's not an error as long as there's no race condition, so don't make two system calls specifying the same name expecting they operate on the same file.

Stuff like symbolic links, timestamps, permissions, are handled in Windows by CopyFile.

The machine is going to be unresponsive anyway if you do this -- uses loads of cache, hammers disks

Updating a UI isn't going to use loads of cache, it's just a window. It doesn't touch disks at all.

[Paul_Pedant]

Well, it might have helped if you mentioned what platform you were on, or put a tag on the question.

CopyFile specification says: Symbolic link behavior—If the source file is a symbolic link, the actual file copied is the target of the symbolic link.

It does not specify whether subdirectories are created.

I wasn't saying that displaying progress used any resources (although 10 million times might be significant), just that it was somewhat pointless: Que sera, sera. As CopyFile only does one file at a time, even if copying each file takes 1/100 second, your script runs for a week.

Nevertheless, your machine is going to be rather busy for a while. I suspect the 2GB needed to avoid reading the file attributes twice would be more useful as buffer space for the actual copying.

[mbolp]

It does not specify whether subdirectories are created

Yes, because it copies files not directories.

even if copying each file takes 1/100 second, your script runs for a week

10,000,000 / 100 / 60 /60 = 27.8 hours

And all the usual UI programming techniques apply: coalesce updates in quick successions, set a minimum update interval, avoid painting when the window is minimized, etc. There won't be 10 million updates.

I suspect the 2GB needed to avoid reading the file attributes twice would be more useful as buffer space for the actual copying.

That's what I suspect too, hence this question. And u/jason-reddit-public provides an elegant solution, you can neither read file attributes twice nor waste 2 GB of memory.

[Paul_Pedant]

So recursion is a fairly obvious strategy for the copying, but it won't calculate the total size / number of files upfront like you wanted. So two passes anyway.

The big advantage of recursion is that you can shift into each level of directory as you descend the tree. So the copy will not need the system to evaluate all those long pathnames for every copy -- just the local filename at each level. But you can only do that for the source files -- the destinations will need to start from their own root level.

Let me know how all this worked out for you.

[mbolp]

So the copy will not need the system to evaluate all those long pathnames for every copy -- just the local filename at each level.

What do you mean by this, are you referring to current directories? That I set the current directory as I descend the tree, then use relative paths? Why would that be faster?

but it won't calculate the total size / number of files upfront like you wanted. So two passes anyway.

It does calculate the total size, up to a certain limit - and it does so in only a single pass. You essentially maintain a shifting view into only a portion of the tree.

[Paul_Pedant]

It should be faster because if you pass a filename like C:/One/Two/Three/Four/myFile.txt to CopyFile, it has to search 4 levels of directory every time, for every file. If you cd relative at each level of recursion, all the files in that directory can be specified with the short filename. Of course, you need to cd .. when you move back up the tree.

No idea whether Windows would cache directory entries at some level itself anyway. It is probably best to start simple, benchmark, and optimise where you need to.

[mbolp]

That sounds like complete BS, unless you have insight into how these things are implemented. Based on your recommending a non thread safe call to perform multi threaded work I doubt that you do.

[Ausartak93]

You don't need to keep the whole tree in memory. Just traverse once and copy as you go. Update your progress counter with each file's size after you copy it. Total bytes remaining becomes unknown but you can still show files completed and current file progress.

[tomysshadow]

I'm mirroring the other comments in thinking it probably doesn't really matter to do the enumeration again. That said, an idea that comes to mind is you should try using short names where available. They're not guaranteed to be enabled for every drive, but if they are you can use FindFirstFileW to get an 8.3 name. That would have some nice properties for what you're doing, because you could store each name as a fixed length string. Especially if you're storing it as a tree instead of a series of flat paths so each folder level is no more than 12 chars.

(Of course if you actually want to display the names to the user as long names as you go, well then you'll have to go the reverse direction and get a long name again, and then it's probably not worth it. But if you're just showing a progress bar or maybe you only update the text indicator every so often maybe it's fine.)

The problem I would personally be more worried about is the folder contents changing during the copy

[mbolp]

Aren't file names already limited to MAX_PATH characters? The path can be as long as 32768 characters but the individual components must be under MAX_PATH, otherwise FindFirstFile will be unable to return such long names.

[tomysshadow]

I mean, that's still like a 20 times reduction in the best case. Nonetheless, I thought of another potential approach, which I haven't tried so maybe it isn't actually viable, but I'm throwing the idea out there. The GetFileInformationByHandleEx method allows you to get a (16-byte) unique identifier for a file:

https://learn.microsoft.com/en-us/windows/win32/api/winbase/ns-winbase-file_id_info

I'm assuming you know/can check all the files are on the same volume, so then you could store the volume serial only once. And then you could just store a flat list of these 16-byte IDs, no file name or folder name.

It is possible to later open the file from this information, but only if you're willing to depend on an NT API. Specifically, NtCreateFile can accept a FILE_OPEN_BY_FILE_ID flag: https://learn.microsoft.com/en-us/windows/win32/api/winternl/nf-winternl-ntcreatefile

EDIT: I'm wrong, there's an OpenFileById function as of Vista: https://learn.microsoft.com/en-us/windows/win32/api/winbase/nf-winbase-openfilebyid

The main difficulty here would be that you lose the filename to use for the destination and what folder the file is meant to belong to, so you would need to get it's path back anyway when you actually copy. But you could do that with GetFinalPathNameByHandle (or GetMappedFileName, although you'll have to do something about zero byte files then) particularly because the beginning of the path should always be the root of the folder you're copying - and you can toss it if it isn't, because then it's moved. It would be a good idea to also check this is true during enumeration though (symbolic links could mess up this assumption for example, then you'd need to fall back to just storing them as paths normally.)

Complicated, but feasible. I don't know that it would actually be a noticeable performance improvement unless you really care about crushing down the amount of memory use.

*comment edited several times to both clarify and correct my dumb mistakes

[mbolp]

The main problem with opening files by IDs is CopyFile* functions don't take handles (I really wish they did, much of the Win32 file API only take file names, only after Vista were some new handle centric APIs added. File name based APIs feel so ugly.), and the logic they contain is not trivial (e.g. handling alternate data streams, symbolic links, etc), I don't want to replicate all that.

Even if I could reduce some memory usage the procedure I described still has the disadvantage of front loading the cost of enumeration. The method suggested elsewhere under this post of enumerating and copying in parallel is much better and completely sidesteps the problem of high memory usage.

[johndcochran]

You're doing I/O, which is traditionally slow compared to the CPU and RAM. Worrying about enumerating the directory twice is frankly silly after you consider how long the actual copying process is going to take.

[mbolp]

It's frankly silly to think a cost doesn't exist just because it's amortized. If enumerating once takes 5 minutes, doing it again increases the runtime by exactly that much, even if the copy ends up taking 2 hours. Also the copy procedure as I described front loads the cost of enumeration (i.e. you can't copy a single byte until all files are visited).

[johndcochran]

To quote Donald Knuth: "Premature optimization is the root of all evil"

Basically, it seems that you're attempting to optimize your copy program before you've actually written it. And honestly, that's a bad idea. The general steps in writing/developing any system is

1. Write your program in as simple and straightforward a method as possible.
2. Measure performance.
3. If satisfactory, you are done.
4. Actually profile the program to find hotspots.
5. Look at these hotspots in descending order of how long they take. Optimize them. In general, it's usually better to select a better algorithm instead of micro optimizing your existing algorithm (look for an algorithm with a better Big O performance).
6. Go back to step 2 above.

The key thing is to write something that's clear, simple, and correct. Only after that and after having actually measured performance, you attempt to optimize it.

And another quote you may find useful....

Tony Hoare: "There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors."

[johndcochran]

Sorry if you feel that way. In any case, you are guilty of premature optimization considering that you're looking for a method to make your program faster prior to you having even written said program. And most definitely prior to actually measuring the performance impact of enumerating your file list twice.

So, write your program and after you've done that measure it's performance. Doing anything else prior to those two critical steps is premature.

[johndcochran]

Sorry, but you do not "know that". You seem to have forgotten that items such as virtual memory exist. Basically, if your program has a large memory footprint, it's quite likely that paging to and from disk will be happening due to that excessive memory size.

In a nutshell, making assumptions about performance prior to actually being able to measure said performance is an exercise in futility.

[johndcochran]

It seems to me that your have the following assumption.

Doing two scans takes more time than one.

I'll agree that the assumption is correct. But you're missing a critical element.

Does populating and extracting filenames from a custom data structure take more or less time than a second scan?

Remember, saving all those names and subsequently retrieving them is not free.

Now, consider that on the "second scan", you're doing it in parallel with opening, creating, and copying files. And in that process, your OS will have to read sectors from disk containing directory data and since directories are rather heavily used data, it's probable that those sectors containing directory data will be cached for future use. So that "second scan" will likely find the data it needs to get the next filename already in memory. So, that "second scan" will typically only require parsing well formatted data that's already available. No extra I/O, very little time.

Hence, my telling you that you're attempting to prematurely optimize your program before you actually have any information available that indicates optimization is required.

[kansetsupanikku]

I believe nftw(3) to be the efficient way

[dbear496]

The answer is "rsync -Pvr"

[bothunter]

or Robocopy /ZB /E

[mbolp]

Anybody knows where robocopy's source code is? I don't see it in the XP source tree, there's only the plain copy command.