# HG changeset patch # User Paul Boddie # Date 1655851971 -7200 # Node ID 7619836f6e6f12a8553c7d720a203237941d0c99 # Parent a554dcf0fef86dfb4357e7dfdabb17c6da52af99 Added some more paging details, adjusted component-related diagrams slightly. diff -r a554dcf0fef8 -r 7619836f6e6f docs/wiki/Components --- a/docs/wiki/Components Sun Jun 19 23:39:05 2022 +0200 +++ b/docs/wiki/Components Wed Jun 22 00:52:51 2022 +0200 @@ -59,9 +59,9 @@ Object [label="MappedFile\nor\nDirectory"]; } - Client1 -> Client2 -> Client3 -> Client4 -> Client5 -> Client6 -> Client7 [arrowhead=none,style=dotted]; - Opener1 -> Opener2 [arrowhead=none,style=dotted]; - OpenerContext1 -> OpenerContext2 -> OpenerContext3 [arrowhead=none,style=dotted]; + Client1 -> Client2 -> Client3 -> Client4 -> Client5 -> Client6 -> Client7 [dir=none,style=dotted]; + Opener1 -> Opener2 [dir=none,style=dotted]; + OpenerContext1 -> OpenerContext2 -> OpenerContext3 [dir=none,style=dotted]; Client1 -> Filesystem [label="open_for_user(user)"]; Filesystem -> Opener1; @@ -129,8 +129,8 @@ } } - Client1 -> Client2 -> Client3 -> Client4 [arrowhead=none,style=dotted]; - Reader1 -> Reader2 -> Reader3 [arrowhead=none,style=dotted]; + Client1 -> Client2 -> Client3 -> Client4 [dir=none,style=dotted]; + Reader1 -> Reader2 -> Reader3 [dir=none,style=dotted]; Client1 -> Directory [label="opendir()"]; Directory -> Reader1; diff -r a554dcf0fef8 -r 7619836f6e6f docs/wiki/Paging --- a/docs/wiki/Paging Sun Jun 19 23:39:05 2022 +0200 +++ b/docs/wiki/Paging Wed Jun 22 00:52:51 2022 +0200 @@ -2,9 +2,8 @@ Within filesystem servers, a number of abstractions are combined to support [[FilesystemAccess|access to filesystem content]] through paging: the delivery -of content to clients in mapped memory. - -The general paging mechanism used to support paging is depicted below. +of content to clients in mapped memory. The general mechanism used to support +paging is depicted below. ######## A graph showing the general paging mechanism @@ -89,22 +88,187 @@ ######## -A [[FilesystemAccess#Pager|Pager]], being a resource that provides filesystem -content to clients for a particular file, requests pages from the PageMapper, -itself having the role of supplying populated pages of content from the given -file. The PageMapper relies on the AccessMap to discover existing pages for -any accessed region of a file, involving the Pages object (or page collection) -to obtain new memory pages where existing pages are not available or are no -longer valid, and requesting the population of such pages through use of the -associated Accessor for the file concerned. +A [[FilesystemAccess#Pager|`Pager`]], being a resource that provides +filesystem content to clients for a particular file, requests pages from the +`PageMapper`, itself having the role of supplying populated pages of content +from the given file. The `PageMapper` relies on the `AccessMap` to discover +existing pages for any accessed region of a file, involving the `Pages` object +(or page collection) to obtain new memory pages where existing pages are not +available or are no longer valid. It also requests the population of such +pages through use of the associated `Accessor` for the file concerned. + +The `Pages` object may either obtain new memory pages from a `Memory` object +or reclaim (or recycle) existing pages from a `PageQueue`, this recording all +pages that have been populated and supplied to clients. Since it may be +desirable to limit the number of pages employed to satisfy file access +operations, the `PageQueue` provides a kind of lending mechanism: pages are +issued to clients and then added to the end of the queue; where no new page +can be supplied by a `Memory` object, the issued page at the head of the queue +is obtained for recycling; ultimately, an issued page will remain valid for +its user (the client accessing its contents) until all pages in front of it in +the queue are themselves recycled and it is then removed from the queue for +recycling. + +When a `PageMapper` requests a page from the `Pages` object and when the +`Pages` object needs to reclaim such a previously issued page, the page +obtained from the head of the queue is removed from the `AccessMap` that +currently owns it. The "owner" of such a page is employing the page to satisfy +requests for content in a region of a particular file. If modified, the page's +contents may be flushed to the underlying file when it is removed from the +owner. As a consequence of its removal, the `AccessMap` will no longer be able +to offer this page to satisfy a request for data in the affected region to its +`PageMapper`. A reclaimed page is then returned to the `PageMapper` requiring +it, and since the page will no longer reside in the `PageQueue`, it will be +exclusively available for that `PageMapper`, being populated with data from +the underlying file and then issued to its client. + +When an `AccessMap` is able to satisfy a request for a page providing access +to a region in a particular file, the `PageMapper` must secure exclusive +access to that page. Otherwise, the possibility exists that the page will be +reclaimed and recycled concurrently by another `PageMapper`. Thus, the +`PageMapper` must request that the page be reserved by the `Pages` object +which in turn removes the page from the `PageQueue`. Since no other party can +now obtain the page independently, it can be issued safely. + +Once a page has been issued to a client by the `Pager`, regardless of how it +was obtained, it must be made available for future reuse. This is achieved by +the `PageMapper` requesting the queuing of the page, with it being added to +the end of the `PageQueue`. + +######## A graph showing concurrency considerations + +{{{#!graphviz +#format svg +#transform notugly +digraph paging_concurrency { + node [fontsize="12.0",fontname="sans-serif",shape=box]; + edge [fontsize="12.0",fontname="sans-serif"]; + rankdir=LR; + + /* First page mapper activities. */ + + subgraph { + rank=min; + + PageMapper1_note [shape=note,style=filled,fillcolor=gold,label="Find\nflexpage"]; + PageMapper1 [label="PageMapper"]; + + PageMapper1_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage"]; + PageMapper1_reserve [label="PageMapper"]; + + PageMapper1_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"]; + PageMapper1_queue [label="PageMapper"]; + + PageMapper1_note -> PageMapper1 [dir=none,style=dotted]; + PageMapper1_reserve_note -> PageMapper1_reserve [dir=none,style=dotted]; + PageMapper1_queue_note -> PageMapper1_queue [dir=none,style=dotted]; + } + + /* Access map usage and flexpage acquisition. */ + + subgraph { + rank=same; + + AccessMap_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ntentatively"]; + AccessMap1 [label="AccessMap"]; + Flexpage1 [label="Flexpage",shape=note,style=dashed]; + Flexpage1_note [shape=note,style=filled,fillcolor=gold,label="Needs reservation\nif found\nby mapper"]; + Flexpage1_reserve [label="Flexpage",shape=note,style=dashed]; + Flexpage1_reserved [label="Flexpage",shape=note]; + Flexpage1_reserved_note [shape=note,style=filled,fillcolor=gold,label="Claimed if\nstill available"]; + Flexpage1_queue [label="Flexpage",shape=note]; -The Pages object may either obtain new memory pages from a Memory object or -reclaim (or recycle) existing pages from a PageQueue, this recording all pages -that have been populated and supplied to clients. Since it may be desirable to -limit the number of pages employed to satisfy file access operations, the -PageQueue provides a kind of lending mechanism: pages are issued to clients -and then added to the end of the queue; where no new page can be supplied by a -Memory object, the issued page at the head of the queue is obtained for -recycling; ultimately, an issued page will remain valid for its user (the -client accessing its contents) until all pages in front of it in the queue are -themselves recycled and it is then removed from the queue for recycling. + AccessMap_note -> AccessMap1 [dir=none,style=dotted]; + Flexpage1 -> Flexpage1_note [dir=none,style=dotted]; + Flexpage1_note -> Flexpage1_reserve [dir=none,style=dotted]; + Flexpage1_reserved -> Flexpage1_reserved_note [dir=none,style=dotted]; + + Flexpage1_reserve -> Flexpage1_reserved [dir=none,style=invis]; + } + + subgraph { + rank=same; + + PageQueue_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ndefinitively"]; + PageQueue [label="PageQueue"]; + Flexpage [shape=note]; + Pages [label="Pages"]; + Pages_note [shape=note,style=filled,fillcolor=gold,label="Claim and\nrecycle\nflexpage"]; + + Flexpage_reserve [label="Flexpage",shape=note]; + Pages_reserve [label="Pages"]; + Pages_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage\nif available"]; + + Pages_queue_note [shape=note,style=filled,fillcolor=gold,label="Queues\nissued\nflexpage"]; + Pages_queue [label="Pages"]; + Flexpage_queued [label="Flexpage",shape=note]; + PageQueue_queued [label="PageQueue"]; + + PageQueue_note -> PageQueue [dir=none,style=dotted]; + Pages -> Pages_note [dir=none,style=dotted]; + Pages_reserve -> Pages_reserve_note [dir=none,style=dotted]; + Pages_queue_note -> Pages_queue [dir=none,style=dotted]; + + Pages_note -> Flexpage_reserve [dir=none,style=invis]; + Pages_reserve_note -> Pages_queue_note [dir=none,style=invis]; + } + + subgraph { + rank=same; + + Flexpage2 [label="Flexpage",shape=note]; + Flexpage2_note [shape=note,style=filled,fillcolor=gold,label="Reserved\nwhen obtained"]; + + Flexpage2 -> Flexpage2_note [dir=none,style=dotted]; + } + + /* Second page mapper activities. */ + + subgraph { + rank=max; + + PageMapper2_note [shape=note,style=filled,fillcolor=gold,label="Obtain\nflexpage"]; + PageMapper2 [label="PageMapper"]; + + PageMapper2_note -> PageMapper2 [dir=none,style=dotted]; + } + + /* First pager dataflow. */ + + PageMapper1 -> AccessMap1 [label="find"]; + AccessMap1 -> Flexpage1 [dir=none]; + Flexpage1 -> PageMapper1; + + PageMapper1_reserve -> Flexpage1_reserve [dir=none]; + Flexpage1_reserve -> Pages_reserve [label="reserve"]; + Pages_reserve -> Flexpage1_reserved [dir=none]; + Flexpage1_reserved -> PageMapper1_reserve; + + PageMapper1_queue -> Flexpage1_queue [dir=none]; + Flexpage1_queue -> Pages_queue [label="queue"]; + + /* Flexpage queuing. */ + + Pages_queue -> Flexpage_queued [dir=none]; + Flexpage_queued -> PageQueue_queued; + + /* Flexpage retrieval from the queue. */ + + Pages -> PageQueue [color="red"]; + PageQueue -> Flexpage [color="red",dir=none]; + Flexpage -> Pages [color="red"]; + Flexpage_reserve -> Pages_reserve; + + /* Flexpage removal from the access map. */ + + Pages -> AccessMap1 [color="red",label="remove"]; + + /* Second pager dataflow. */ + + PageMapper2 -> Pages [color="red"]; + Pages -> Flexpage2 [color="red",dir=none]; + Flexpage2 -> PageMapper2 [color="red"]; +} +}}} + +########