Copy-on-write: Difference between revisions

Revision as of 18:22, 7 August 2014

Latest revision as of 03:40, 13 August 2025

(136 intermediate revisions by 86 users not shown)

Line 1:

{{Short description|Programming technique for efficiently duplicating data}}

{{one source|date=January 2013}}

{{Use dmy dates|date=November 2023}}

'''Copy-on-write''' (sometimes referred to as "COW") is an [[Optimization (computer science)|optimization]] strategy used in [[computer programming]]. Copy-on-write stems from the understanding that when multiple separate tasks use initially identical copies of some information (i.e., data stored in computer memory or disk storage), treating it as local data that they may occasionally need to modify, then it is not necessary to immediately create separate copies of that information for each task. Instead they can all be given pointers to the same resource, with the provision that on the first occasion where they need to modify the data, they must first create a local copy on which to perform the modification (the original resource remains unchanged). When there are many separate processes all using the same resource, each with a small likelihood of having to modify it at all, then it is possible to make significant resource savings by sharing resources this way. Copy-on-write is the name given to the policy that whenever a task attempts to make a change to the shared information, it should first create a separate (private) copy of that information to prevent its changes from becoming visible to all the other tasks. If this policy is enforced by the operating system kernel, then the fact of being given a reference to shared information rather than a private copy can be [[transparency (human–computer interaction)|transparent]] to all tasks, whether they need to modify the information or not.<ref name="Kongens Lyngby 2010">{{cite web |last=Kasampalis |first=Sakis |title=Copy On Write Based File Systems Performance Analysis And Implementation |url=http://faif.objectis.net/download-copy-on-write-based-file-systems |page=19 |format=pdf |year=2010 |deadurl=no |accessdate=11 January 2013}}</ref>

'''Copy-on-write''' ('''COW'''), also called '''implicit sharing'''<ref>{{cite web |title=Implicit Sharing |url=https://doc.qt.io/qt-5/implicit-sharing.html |website=Qt Project |access-date=10 November 2023 |archive-date=8 February 2024 |archive-url=https://web.archive.org/web/20240208175543/https://doc.qt.io/qt-5/implicit-sharing.html |url-status=live }}</ref> or '''shadowing''',<ref>{{cite journal |last=Rodeh |first=Ohad |title=B-Trees, Shadowing, and Clones |journal=ACM Transactions on Storage |volume=3 |issue=4 |date=1 February 2008 |page=1 |citeseerx=10.1.1.161.6863 |s2cid=207166167 |doi=10.1145/1326542.1326544 |url=http://liw.fi/larch/ohad-btrees-shadowing-clones.pdf |archive-url=https://web.archive.org/web/20170102212904/http://liw.fi/larch/ohad-btrees-shadowing-clones.pdf |archive-date=2 January 2017 |access-date=10 November 2023 }}</ref> is a [[Resource management (computing)|resource-management]] technique<ref name="Linux">{{cite book |last1=Bovet |first1=Daniel Pierre |last2=Cesati |first2=Marco |date=1 January 2002 |title=Understanding the Linux Kernel |url=https://books.google.com/books?id=9yIEji1UheIC&q=%22copy%20on%20write%22&pg=PA295 |publisher=O'Reilly Media |isbn=9780596002138 |page=295 |access-date=10 November 2023 |archive-date=15 September 2024 |archive-url=https://web.archive.org/web/20240915132745/https://books.google.com/books?id=9yIEji1UheIC&q=%22copy%20on%20write%22&pg=PA295#v=snippet&q=%22copy%20on%20write%22&f=false |url-status=live }}</ref> used in [[computer programming|programming]] to manage shared data efficiently. Instead of copying data right away when multiple programs use it, the same data is shared between programs until one tries to modify it. If no changes are made, no private copy is created, saving [[System resource#General resources|resources]].<ref name="Linux" /> A copy is only made when needed, ensuring each program has its own version when modifications occur. This technique is commonly applied to memory, files, and data structures.

==Copy-on-write in virtual memory management==

Copy-on-write finds its main use in [[virtual memory]] [[operating system]]s; when a [[computer process|process]] creates a copy of itself, the pages in [[computer storage|memory]] that might be modified by either the process or its copy are marked copy-on-write. When one process modifies the memory, the operating system's [[kernel (computing)|kernel]] intercepts the operation and copies the memory thus a change in the memory of one process is not visible in another's.

==Copy-on-write inIn virtual memory management==

Another use involves the [[calloc]] function. This can be implemented by means of having a page of physical memory filled with zeros. When the memory is allocated, all the pages returned refer to the page of zeros and are all marked copy-on-write. This way, the amount of physical memory allocated for the process does not increase until data is written. This is typically done only for larger allocations.

Copy-on-write finds its main use in [[operating system]]s, sharing the [[physical memory]] of computers running multiple [[Process (computing)|processes]], in the implementation of the [[Fork (system call)|fork() system call]]. Typically, the new process does not modify any memory and immediately executes a new process, replacing the address space entirely. It would waste processor time and memory to copy all of the old process's memory during the fork only to immediately discard the copy.<ref>{{Cite book |last=Silberschatz |first=Abraham |title=Operating System Concepts |last2=Galvin, Peter B. |last3=Gagne |first3=Greg |publisher=Wiley |year=2018 |isbn=978-1119456339 |edition=10th |pages=120–123}}</ref>

Copy-on-write can be implemented byefficiently notifyingusing the [[memorypage management unit|MMUtable]] thatby marking certain pages inof the[[Computer process'sstorage|memory]] address space areas read-only. and keeping a count of the number of references to the page. When data is written to these pages, the MMUoperating-system raises[[Kernel an(operating exceptionsystem)|kernel]] whichintercepts isthe handledwrite byattempt and allocates a new physical page, initialized with the kernelcopy-on-write data, whichalthough allocatesthe allocation can be skipped if there is only one reference. The kernel then updates the page table with the new space(writable) inpage, physicaldecrements memorythe number of references, and makesperforms the pagewrite. beingThe writtennew correspondallocation toensures that newa ___locationchange in physicalthe memory of one process is not visible in another's.{{Citation needed|date=November 2023}}

AnotherThe usecopy-on-write involvestechnique thecan [[calloc]]be function.extended to Thissupport canefficient be[[memory implementedallocation]] by meanskeeping of having aone page of [[physical memory]] filled with zeros. When the memory is allocated, all the pages returned refer to the page of zeros and are all marked copy-on-write. This way, the amount of physical memory is not allocated for the process does not increase until data is written, allowing processes to reserve more virtual memory than physical memory and use memory sparsely, at the risk of running out of virtual address space. The Thiscombined algorithm is typicallysimilar doneto only[[demand forpaging]].<ref largername="Linux" allocations./>

One major advantage of COW is the ability to use memory sparsely. Because the usage of physical memory only increases as data is stored in it, very efficient [[hash table]]s can be implemented which only use little more physical memory than is necessary to store the objects they contain. However, such programs run the risk of running out of virtual address space — virtual pages unused by the hash table cannot be used by other parts of the program{{Citation needed|date=January 2013}}. The main problem with COW at the kernel level is the complexity it adds, but the concerns are similar to those raised by more basic virtual-memory concerns such as swapping pages to disk; when the kernel writes to pages, it must copy any such pages marked copy-on-write.

Copy-on-write pages are also used in the [[Linux kernel]]'s [[Kernel same-page merging|same-page merging]] feature.<ref>{{Cite web |last=Abbas |first=Ali |title=The Kernel Samepage Merging Process |url=http://alouche.net/blog/2011/07/18/the-kernel-samepage-merging-process/ |url-status=usurped |archive-url=https://web.archive.org/web/20160808174912/http://alouche.net/blog/2011/07/18/the-kernel-samepage-merging-process/ |archive-date=8 August 2016 |access-date=10 November 2023 |website=alouche.net}}</ref>

== Copy-on-write in storage media ==

==In software==

COW may also be used as the underlying mechanism for disk storage [[Snapshot (computer storage)|snapshots]] such as those provided by [[logical volume management]], Microsoft [[Shadow Copy|Volume Shadow Copy Service]] or file systems such as [[btrfs]] in [[Linux]].

{{Expand section|date=October 2017}}

COW is also used outside the kernel, in [[Library (computer science)|library]], [[Application software|application]], and [[System software|system]] code. The [[String (C++)|string]] class provided by the [[C++ standard library]], for example, was

Copy-on-write is also used in maintenance of instant snapshot on database servers like Microsoft SQL Server 2005. Instant snapshots preserve a static view of a database by storing a pre-modification copy of data when underlying data are updated. Instant snapshots are used for testing uses or moment-dependent reports and should not be used to replace backups. On the other hand, snapshots enable database back-ups in a consistent state without taking them offline.

===Examples===

The copy-on-write technique can be used to emulate a read-write storage on media that require [[wear leveling]] or are physically [[write once read many]].

The [[String (C++)|string]] class provided by the [[C++ standard library]] was specifically designed to allow copy-on-write implementations in the initial C++98 standard,<ref name="meyers">{{cite book |first=Scott |last=Meyers |author-link=Scott Meyers |date=2012 |title=Effective STL |publisher=Addison-Wesley |pages=64–65 |isbn=9780132979184 }}</ref> but not in the newer C++11 standard:<ref>{{cite web |title=Concurrency Modifications to Basic String |url=https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2534.html |website=Open Standards |access-date=10 November 2023 |archive-date=10 November 2023 |archive-url=https://web.archive.org/web/20231110024434/https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2534.html |url-status=live }}</ref>

<sourcesyntaxhighlight lang="cpp">

std::string x("Hello");

std::string y = x; // x and y use the same buffer.

The [[qcow2]] (QEMU copy on write) file format for disk images uses the copy-on-write principle to delay allocation of storage until it is actually needed. This reduces the actual disk space required to store disk images.

y += ", World!"; // nowNow y uses a different buffer; x still uses the same old buffer.

Some [[Live CD]]s (and [[Live USB]]s) use copy-on-write techniques to give the impression of being able to add and delete files in any directory,

</syntaxhighlight>

without actually making any changes to the CD (or USB flash drive).

In the [[PHP]] programming language, all types except references are implemented as copy-on-write. For example, strings and arrays are passed by reference, but when modified, they are duplicated if they have non-zero reference counts. This allows them to act as value types without the performance problems of copying on assignment or making them immutable.<ref>{{cite web |last1=Pauli |first1=Julien |last2=Ferrara |first2=Anthony |last3=Popov |first3=Nikita |title=Memory management |date=2013 |url=https://www.phpinternalsbook.com/php5/zvals/memory_management.html#reference-counting-and-copy-on-write |website=PhpInternalsBook.com |access-date=10 November 2023 |archive-date=10 November 2023 |archive-url=https://web.archive.org/web/20231110024435/https://www.phpinternalsbook.com/php5/zvals/memory_management.html#reference-counting-and-copy-on-write |url-status=live }}</ref>

==Other applications of copy-on-write==

COW is also used outside the kernel, in [[Library (computer science)|library]], [[Application software|application]] and [[System software|system]] code. The [[String (C++)|string]] class provided by the [[C++ standard library]], for example, was

specifically designed to allow copy-on-write implementations in the C++98/03 standards{{Citation needed|date=September 2013}}, but not in the newer C++11 standard:

In the [[Qt (software)|Qt]] framework, many types are copy-on-write ("implicitly shared" in Qt's terms). Qt uses atomic [[compare-and-swap]] operations to increment or decrement the internal reference counter. Since the copies are cheap, Qt types can often be safely used by [[Multithreading (computer architecture)|multiple threads]] without the need of [[Lock (computer science)|locking mechanisms]] such as [[Mutual exclusion|mutexes]]. The benefits of COW are thus valid in both single- and multithreaded systems.<ref>{{cite web |title=Threads and Implicitly Shared Classes |website=Qt Project |url=https://doc.qt.io/qt-5/threads-modules.html#threads-and-implicitly-shared-classes |access-date=10 November 2023 |archive-date=3 December 2023 |archive-url=https://web.archive.org/web/20231203002914/https://doc.qt.io/QT-5/threads-modules.html#threads-and-implicitly-shared-classes |url-status=live }}</ref>

<source lang="cpp">

std::string x("Hello");

==In computer storage==

std::string y = x; // x and y use the same buffer

COW is used as the underlying mechanism in file systems like [[ZFS]], [[Btrfs]],<ref>{{cite web |last=Kasampalis |first=Sakis |date=2010 |title=Copy-on-Write Based File Systems Performance Analysis and Implementation |page=19 |url=https://sakisk.me/files/copy-on-write-based-file-systems.pdf |access-date=10 November 2023 |archive-date=5 May 2024 |archive-url=https://web.archive.org/web/20240505220510/https://sakisk.me/files/copy-on-write-based-file-systems.pdf |url-status=live }}</ref> [[ReFS]], and [[Bcachefs]], as well as in [[logical volume management]] and database servers such as [[Microsoft SQL Server#Replication Services|Microsoft SQL Server]].

In traditional file systems, modifying a file overwrites the original data blocks in place. In a copy-on-write (COW) file system, the original blocks remain unchanged. When part of a file is modified, only the affected blocks are written to new locations, and metadata is updated to point to them, preserving the original version until it’s no longer needed. This approach enables features like [[Snapshot (computer storage)|snapshots]], which capture the state of a file at a specific time without consuming much additional space. Snapshots typically store only the modified data and are kept close to the original. However, they are considered a weak form of [[incremental backup]] and cannot replace a full backup.<ref>{{cite web |last=Chien |first=Tim |title=Snapshots Are NOT Backups |url=https://www.oracle.com/database/technologies/rman-fra-snapshot.html |website=Oracle.com |publisher=Oracle |access-date=10 November 2023 |archive-date=10 November 2023 |archive-url=https://web.archive.org/web/20231110024434/https://www.oracle.com/database/technologies/rman-fra-snapshot.html |url-status=live }}</ref>

y += ", World!"; // now y uses a different buffer

// x still uses the same old buffer

</source>

In the [[PHP]] programming language, some types are implemented as copy-on-write. For example, strings and arrays are passed by reference, but when modified, they are duplicated if they have non-zero reference counts. This allows them to act as value types without the performance problems of copying on assignment or making them immutable.

In [[multithreaded]] systems, COW can be implemented without the use of traditional [[Lock (software engineering)|locking]] and instead use [[compare-and-swap]] to increment or decrement the internal reference counter. Since the original resource will never be altered, it can safely be copied by multiple threads (after the reference count was increased) without the need of performance-expensive locking such as mutexes. If the reference counter turns 0, then by definition only 1 thread is holding a reference so the resource can safely be de-allocated from memory, again without the use of performance-expensive locking mechanisms. The benefit of not having to copy the resource (and the resulting performance gain over traditional deep-copying) will therefore be valid in both single- and multithreaded systems.

==See also==

* [[Flyweight patternAllocate-on-flush]]

* [[Dirty COW]] – a computer security vulnerability for the Linux kernel

*[[Allocate-on-flush]]

* [[DemandFlyweight pagingpattern]]

* [[Memory management]]

* [[Persistent data structure]]

*[[Virtual memory|Memory mapping]]

* [[Wear leveling]]

==References==

{{Reflist}}

<references />

==External links==

* {{cite web |title=A history of copy-on-write memory management |url=https://obvious.services.net/2011/01/history-of-copy-on-write-memory.html |website=A keen grasp of the obvious |access-date=18 November 2024 |date=21 January 2011}}

{{File systems}}

[[Category:Virtual memory]]

[[Category:Virtualization software]]

[[Category:Software optimization]]

[[Category:Articles with example C++ code]]

[[Category:Computer data storage]]

[[Category:Software optimization]]

*[[Category:Virtual memory|Memory mapping]]

[[Category:Virtual memoryVirtualization]]