1.1 --- a/docs/wiki/Paging Sun Jun 19 23:39:05 2022 +0200
1.2 +++ b/docs/wiki/Paging Wed Jun 22 00:52:51 2022 +0200
1.3 @@ -2,9 +2,8 @@
1.4
1.5 Within filesystem servers, a number of abstractions are combined to support
1.6 [[FilesystemAccess|access to filesystem content]] through paging: the delivery
1.7 -of content to clients in mapped memory.
1.8 -
1.9 -The general paging mechanism used to support paging is depicted below.
1.10 +of content to clients in mapped memory. The general mechanism used to support
1.11 +paging is depicted below.
1.12
1.13 ######## A graph showing the general paging mechanism
1.14
1.15 @@ -89,22 +88,187 @@
1.16
1.17 ########
1.18
1.19 -A [[FilesystemAccess#Pager|Pager]], being a resource that provides filesystem
1.20 -content to clients for a particular file, requests pages from the PageMapper,
1.21 -itself having the role of supplying populated pages of content from the given
1.22 -file. The PageMapper relies on the AccessMap to discover existing pages for
1.23 -any accessed region of a file, involving the Pages object (or page collection)
1.24 -to obtain new memory pages where existing pages are not available or are no
1.25 -longer valid, and requesting the population of such pages through use of the
1.26 -associated Accessor for the file concerned.
1.27 +A [[FilesystemAccess#Pager|`Pager`]], being a resource that provides
1.28 +filesystem content to clients for a particular file, requests pages from the
1.29 +`PageMapper`, itself having the role of supplying populated pages of content
1.30 +from the given file. The `PageMapper` relies on the `AccessMap` to discover
1.31 +existing pages for any accessed region of a file, involving the `Pages` object
1.32 +(or page collection) to obtain new memory pages where existing pages are not
1.33 +available or are no longer valid. It also requests the population of such
1.34 +pages through use of the associated `Accessor` for the file concerned.
1.35 +
1.36 +The `Pages` object may either obtain new memory pages from a `Memory` object
1.37 +or reclaim (or recycle) existing pages from a `PageQueue`, this recording all
1.38 +pages that have been populated and supplied to clients. Since it may be
1.39 +desirable to limit the number of pages employed to satisfy file access
1.40 +operations, the `PageQueue` provides a kind of lending mechanism: pages are
1.41 +issued to clients and then added to the end of the queue; where no new page
1.42 +can be supplied by a `Memory` object, the issued page at the head of the queue
1.43 +is obtained for recycling; ultimately, an issued page will remain valid for
1.44 +its user (the client accessing its contents) until all pages in front of it in
1.45 +the queue are themselves recycled and it is then removed from the queue for
1.46 +recycling.
1.47 +
1.48 +When a `PageMapper` requests a page from the `Pages` object and when the
1.49 +`Pages` object needs to reclaim such a previously issued page, the page
1.50 +obtained from the head of the queue is removed from the `AccessMap` that
1.51 +currently owns it. The "owner" of such a page is employing the page to satisfy
1.52 +requests for content in a region of a particular file. If modified, the page's
1.53 +contents may be flushed to the underlying file when it is removed from the
1.54 +owner. As a consequence of its removal, the `AccessMap` will no longer be able
1.55 +to offer this page to satisfy a request for data in the affected region to its
1.56 +`PageMapper`. A reclaimed page is then returned to the `PageMapper` requiring
1.57 +it, and since the page will no longer reside in the `PageQueue`, it will be
1.58 +exclusively available for that `PageMapper`, being populated with data from
1.59 +the underlying file and then issued to its client.
1.60 +
1.61 +When an `AccessMap` is able to satisfy a request for a page providing access
1.62 +to a region in a particular file, the `PageMapper` must secure exclusive
1.63 +access to that page. Otherwise, the possibility exists that the page will be
1.64 +reclaimed and recycled concurrently by another `PageMapper`. Thus, the
1.65 +`PageMapper` must request that the page be reserved by the `Pages` object
1.66 +which in turn removes the page from the `PageQueue`. Since no other party can
1.67 +now obtain the page independently, it can be issued safely.
1.68 +
1.69 +Once a page has been issued to a client by the `Pager`, regardless of how it
1.70 +was obtained, it must be made available for future reuse. This is achieved by
1.71 +the `PageMapper` requesting the queuing of the page, with it being added to
1.72 +the end of the `PageQueue`.
1.73 +
1.74 +######## A graph showing concurrency considerations
1.75 +
1.76 +{{{#!graphviz
1.77 +#format svg
1.78 +#transform notugly
1.79 +digraph paging_concurrency {
1.80 + node [fontsize="12.0",fontname="sans-serif",shape=box];
1.81 + edge [fontsize="12.0",fontname="sans-serif"];
1.82 + rankdir=LR;
1.83 +
1.84 + /* First page mapper activities. */
1.85 +
1.86 + subgraph {
1.87 + rank=min;
1.88 +
1.89 + PageMapper1_note [shape=note,style=filled,fillcolor=gold,label="Find\nflexpage"];
1.90 + PageMapper1 [label="PageMapper"];
1.91 +
1.92 + PageMapper1_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage"];
1.93 + PageMapper1_reserve [label="PageMapper"];
1.94 +
1.95 + PageMapper1_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"];
1.96 + PageMapper1_queue [label="PageMapper"];
1.97 +
1.98 + PageMapper1_note -> PageMapper1 [dir=none,style=dotted];
1.99 + PageMapper1_reserve_note -> PageMapper1_reserve [dir=none,style=dotted];
1.100 + PageMapper1_queue_note -> PageMapper1_queue [dir=none,style=dotted];
1.101 + }
1.102 +
1.103 + /* Access map usage and flexpage acquisition. */
1.104 +
1.105 + subgraph {
1.106 + rank=same;
1.107 +
1.108 + AccessMap_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ntentatively"];
1.109 + AccessMap1 [label="AccessMap"];
1.110 + Flexpage1 [label="Flexpage",shape=note,style=dashed];
1.111 + Flexpage1_note [shape=note,style=filled,fillcolor=gold,label="Needs reservation\nif found\nby mapper"];
1.112 + Flexpage1_reserve [label="Flexpage",shape=note,style=dashed];
1.113 + Flexpage1_reserved [label="Flexpage",shape=note];
1.114 + Flexpage1_reserved_note [shape=note,style=filled,fillcolor=gold,label="Claimed if\nstill available"];
1.115 + Flexpage1_queue [label="Flexpage",shape=note];
1.116
1.117 -The Pages object may either obtain new memory pages from a Memory object or
1.118 -reclaim (or recycle) existing pages from a PageQueue, this recording all pages
1.119 -that have been populated and supplied to clients. Since it may be desirable to
1.120 -limit the number of pages employed to satisfy file access operations, the
1.121 -PageQueue provides a kind of lending mechanism: pages are issued to clients
1.122 -and then added to the end of the queue; where no new page can be supplied by a
1.123 -Memory object, the issued page at the head of the queue is obtained for
1.124 -recycling; ultimately, an issued page will remain valid for its user (the
1.125 -client accessing its contents) until all pages in front of it in the queue are
1.126 -themselves recycled and it is then removed from the queue for recycling.
1.127 + AccessMap_note -> AccessMap1 [dir=none,style=dotted];
1.128 + Flexpage1 -> Flexpage1_note [dir=none,style=dotted];
1.129 + Flexpage1_note -> Flexpage1_reserve [dir=none,style=dotted];
1.130 + Flexpage1_reserved -> Flexpage1_reserved_note [dir=none,style=dotted];
1.131 +
1.132 + Flexpage1_reserve -> Flexpage1_reserved [dir=none,style=invis];
1.133 + }
1.134 +
1.135 + subgraph {
1.136 + rank=same;
1.137 +
1.138 + PageQueue_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ndefinitively"];
1.139 + PageQueue [label="PageQueue"];
1.140 + Flexpage [shape=note];
1.141 + Pages [label="Pages"];
1.142 + Pages_note [shape=note,style=filled,fillcolor=gold,label="Claim and\nrecycle\nflexpage"];
1.143 +
1.144 + Flexpage_reserve [label="Flexpage",shape=note];
1.145 + Pages_reserve [label="Pages"];
1.146 + Pages_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage\nif available"];
1.147 +
1.148 + Pages_queue_note [shape=note,style=filled,fillcolor=gold,label="Queues\nissued\nflexpage"];
1.149 + Pages_queue [label="Pages"];
1.150 + Flexpage_queued [label="Flexpage",shape=note];
1.151 + PageQueue_queued [label="PageQueue"];
1.152 +
1.153 + PageQueue_note -> PageQueue [dir=none,style=dotted];
1.154 + Pages -> Pages_note [dir=none,style=dotted];
1.155 + Pages_reserve -> Pages_reserve_note [dir=none,style=dotted];
1.156 + Pages_queue_note -> Pages_queue [dir=none,style=dotted];
1.157 +
1.158 + Pages_note -> Flexpage_reserve [dir=none,style=invis];
1.159 + Pages_reserve_note -> Pages_queue_note [dir=none,style=invis];
1.160 + }
1.161 +
1.162 + subgraph {
1.163 + rank=same;
1.164 +
1.165 + Flexpage2 [label="Flexpage",shape=note];
1.166 + Flexpage2_note [shape=note,style=filled,fillcolor=gold,label="Reserved\nwhen obtained"];
1.167 +
1.168 + Flexpage2 -> Flexpage2_note [dir=none,style=dotted];
1.169 + }
1.170 +
1.171 + /* Second page mapper activities. */
1.172 +
1.173 + subgraph {
1.174 + rank=max;
1.175 +
1.176 + PageMapper2_note [shape=note,style=filled,fillcolor=gold,label="Obtain\nflexpage"];
1.177 + PageMapper2 [label="PageMapper"];
1.178 +
1.179 + PageMapper2_note -> PageMapper2 [dir=none,style=dotted];
1.180 + }
1.181 +
1.182 + /* First pager dataflow. */
1.183 +
1.184 + PageMapper1 -> AccessMap1 [label="find"];
1.185 + AccessMap1 -> Flexpage1 [dir=none];
1.186 + Flexpage1 -> PageMapper1;
1.187 +
1.188 + PageMapper1_reserve -> Flexpage1_reserve [dir=none];
1.189 + Flexpage1_reserve -> Pages_reserve [label="reserve"];
1.190 + Pages_reserve -> Flexpage1_reserved [dir=none];
1.191 + Flexpage1_reserved -> PageMapper1_reserve;
1.192 +
1.193 + PageMapper1_queue -> Flexpage1_queue [dir=none];
1.194 + Flexpage1_queue -> Pages_queue [label="queue"];
1.195 +
1.196 + /* Flexpage queuing. */
1.197 +
1.198 + Pages_queue -> Flexpage_queued [dir=none];
1.199 + Flexpage_queued -> PageQueue_queued;
1.200 +
1.201 + /* Flexpage retrieval from the queue. */
1.202 +
1.203 + Pages -> PageQueue [color="red"];
1.204 + PageQueue -> Flexpage [color="red",dir=none];
1.205 + Flexpage -> Pages [color="red"];
1.206 + Flexpage_reserve -> Pages_reserve;
1.207 +
1.208 + /* Flexpage removal from the access map. */
1.209 +
1.210 + Pages -> AccessMap1 [color="red",label="remove"];
1.211 +
1.212 + /* Second pager dataflow. */
1.213 +
1.214 + PageMapper2 -> Pages [color="red"];
1.215 + Pages -> Flexpage2 [color="red",dir=none];
1.216 + Flexpage2 -> PageMapper2 [color="red"];
1.217 +}
1.218 +}}}
1.219 +
1.220 +########