1.1 --- a/docs/wiki/Components Sun Jun 19 23:39:05 2022 +0200
1.2 +++ b/docs/wiki/Components Wed Jun 22 00:52:51 2022 +0200
1.3 @@ -59,9 +59,9 @@
1.4 Object [label="MappedFile\nor\nDirectory"];
1.5 }
1.6
1.7 - Client1 -> Client2 -> Client3 -> Client4 -> Client5 -> Client6 -> Client7 [arrowhead=none,style=dotted];
1.8 - Opener1 -> Opener2 [arrowhead=none,style=dotted];
1.9 - OpenerContext1 -> OpenerContext2 -> OpenerContext3 [arrowhead=none,style=dotted];
1.10 + Client1 -> Client2 -> Client3 -> Client4 -> Client5 -> Client6 -> Client7 [dir=none,style=dotted];
1.11 + Opener1 -> Opener2 [dir=none,style=dotted];
1.12 + OpenerContext1 -> OpenerContext2 -> OpenerContext3 [dir=none,style=dotted];
1.13
1.14 Client1 -> Filesystem [label="open_for_user(user)"];
1.15 Filesystem -> Opener1;
1.16 @@ -129,8 +129,8 @@
1.17 }
1.18 }
1.19
1.20 - Client1 -> Client2 -> Client3 -> Client4 [arrowhead=none,style=dotted];
1.21 - Reader1 -> Reader2 -> Reader3 [arrowhead=none,style=dotted];
1.22 + Client1 -> Client2 -> Client3 -> Client4 [dir=none,style=dotted];
1.23 + Reader1 -> Reader2 -> Reader3 [dir=none,style=dotted];
1.24
1.25 Client1 -> Directory [label="opendir()"];
1.26 Directory -> Reader1;
2.1 --- a/docs/wiki/Paging Sun Jun 19 23:39:05 2022 +0200
2.2 +++ b/docs/wiki/Paging Wed Jun 22 00:52:51 2022 +0200
2.3 @@ -2,9 +2,8 @@
2.4
2.5 Within filesystem servers, a number of abstractions are combined to support
2.6 [[FilesystemAccess|access to filesystem content]] through paging: the delivery
2.7 -of content to clients in mapped memory.
2.8 -
2.9 -The general paging mechanism used to support paging is depicted below.
2.10 +of content to clients in mapped memory. The general mechanism used to support
2.11 +paging is depicted below.
2.12
2.13 ######## A graph showing the general paging mechanism
2.14
2.15 @@ -89,22 +88,187 @@
2.16
2.17 ########
2.18
2.19 -A [[FilesystemAccess#Pager|Pager]], being a resource that provides filesystem
2.20 -content to clients for a particular file, requests pages from the PageMapper,
2.21 -itself having the role of supplying populated pages of content from the given
2.22 -file. The PageMapper relies on the AccessMap to discover existing pages for
2.23 -any accessed region of a file, involving the Pages object (or page collection)
2.24 -to obtain new memory pages where existing pages are not available or are no
2.25 -longer valid, and requesting the population of such pages through use of the
2.26 -associated Accessor for the file concerned.
2.27 +A [[FilesystemAccess#Pager|`Pager`]], being a resource that provides
2.28 +filesystem content to clients for a particular file, requests pages from the
2.29 +`PageMapper`, itself having the role of supplying populated pages of content
2.30 +from the given file. The `PageMapper` relies on the `AccessMap` to discover
2.31 +existing pages for any accessed region of a file, involving the `Pages` object
2.32 +(or page collection) to obtain new memory pages where existing pages are not
2.33 +available or are no longer valid. It also requests the population of such
2.34 +pages through use of the associated `Accessor` for the file concerned.
2.35 +
2.36 +The `Pages` object may either obtain new memory pages from a `Memory` object
2.37 +or reclaim (or recycle) existing pages from a `PageQueue`, this recording all
2.38 +pages that have been populated and supplied to clients. Since it may be
2.39 +desirable to limit the number of pages employed to satisfy file access
2.40 +operations, the `PageQueue` provides a kind of lending mechanism: pages are
2.41 +issued to clients and then added to the end of the queue; where no new page
2.42 +can be supplied by a `Memory` object, the issued page at the head of the queue
2.43 +is obtained for recycling; ultimately, an issued page will remain valid for
2.44 +its user (the client accessing its contents) until all pages in front of it in
2.45 +the queue are themselves recycled and it is then removed from the queue for
2.46 +recycling.
2.47 +
2.48 +When a `PageMapper` requests a page from the `Pages` object and when the
2.49 +`Pages` object needs to reclaim such a previously issued page, the page
2.50 +obtained from the head of the queue is removed from the `AccessMap` that
2.51 +currently owns it. The "owner" of such a page is employing the page to satisfy
2.52 +requests for content in a region of a particular file. If modified, the page's
2.53 +contents may be flushed to the underlying file when it is removed from the
2.54 +owner. As a consequence of its removal, the `AccessMap` will no longer be able
2.55 +to offer this page to satisfy a request for data in the affected region to its
2.56 +`PageMapper`. A reclaimed page is then returned to the `PageMapper` requiring
2.57 +it, and since the page will no longer reside in the `PageQueue`, it will be
2.58 +exclusively available for that `PageMapper`, being populated with data from
2.59 +the underlying file and then issued to its client.
2.60 +
2.61 +When an `AccessMap` is able to satisfy a request for a page providing access
2.62 +to a region in a particular file, the `PageMapper` must secure exclusive
2.63 +access to that page. Otherwise, the possibility exists that the page will be
2.64 +reclaimed and recycled concurrently by another `PageMapper`. Thus, the
2.65 +`PageMapper` must request that the page be reserved by the `Pages` object
2.66 +which in turn removes the page from the `PageQueue`. Since no other party can
2.67 +now obtain the page independently, it can be issued safely.
2.68 +
2.69 +Once a page has been issued to a client by the `Pager`, regardless of how it
2.70 +was obtained, it must be made available for future reuse. This is achieved by
2.71 +the `PageMapper` requesting the queuing of the page, with it being added to
2.72 +the end of the `PageQueue`.
2.73 +
2.74 +######## A graph showing concurrency considerations
2.75 +
2.76 +{{{#!graphviz
2.77 +#format svg
2.78 +#transform notugly
2.79 +digraph paging_concurrency {
2.80 + node [fontsize="12.0",fontname="sans-serif",shape=box];
2.81 + edge [fontsize="12.0",fontname="sans-serif"];
2.82 + rankdir=LR;
2.83 +
2.84 + /* First page mapper activities. */
2.85 +
2.86 + subgraph {
2.87 + rank=min;
2.88 +
2.89 + PageMapper1_note [shape=note,style=filled,fillcolor=gold,label="Find\nflexpage"];
2.90 + PageMapper1 [label="PageMapper"];
2.91 +
2.92 + PageMapper1_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage"];
2.93 + PageMapper1_reserve [label="PageMapper"];
2.94 +
2.95 + PageMapper1_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"];
2.96 + PageMapper1_queue [label="PageMapper"];
2.97 +
2.98 + PageMapper1_note -> PageMapper1 [dir=none,style=dotted];
2.99 + PageMapper1_reserve_note -> PageMapper1_reserve [dir=none,style=dotted];
2.100 + PageMapper1_queue_note -> PageMapper1_queue [dir=none,style=dotted];
2.101 + }
2.102 +
2.103 + /* Access map usage and flexpage acquisition. */
2.104 +
2.105 + subgraph {
2.106 + rank=same;
2.107 +
2.108 + AccessMap_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ntentatively"];
2.109 + AccessMap1 [label="AccessMap"];
2.110 + Flexpage1 [label="Flexpage",shape=note,style=dashed];
2.111 + Flexpage1_note [shape=note,style=filled,fillcolor=gold,label="Needs reservation\nif found\nby mapper"];
2.112 + Flexpage1_reserve [label="Flexpage",shape=note,style=dashed];
2.113 + Flexpage1_reserved [label="Flexpage",shape=note];
2.114 + Flexpage1_reserved_note [shape=note,style=filled,fillcolor=gold,label="Claimed if\nstill available"];
2.115 + Flexpage1_queue [label="Flexpage",shape=note];
2.116
2.117 -The Pages object may either obtain new memory pages from a Memory object or
2.118 -reclaim (or recycle) existing pages from a PageQueue, this recording all pages
2.119 -that have been populated and supplied to clients. Since it may be desirable to
2.120 -limit the number of pages employed to satisfy file access operations, the
2.121 -PageQueue provides a kind of lending mechanism: pages are issued to clients
2.122 -and then added to the end of the queue; where no new page can be supplied by a
2.123 -Memory object, the issued page at the head of the queue is obtained for
2.124 -recycling; ultimately, an issued page will remain valid for its user (the
2.125 -client accessing its contents) until all pages in front of it in the queue are
2.126 -themselves recycled and it is then removed from the queue for recycling.
2.127 + AccessMap_note -> AccessMap1 [dir=none,style=dotted];
2.128 + Flexpage1 -> Flexpage1_note [dir=none,style=dotted];
2.129 + Flexpage1_note -> Flexpage1_reserve [dir=none,style=dotted];
2.130 + Flexpage1_reserved -> Flexpage1_reserved_note [dir=none,style=dotted];
2.131 +
2.132 + Flexpage1_reserve -> Flexpage1_reserved [dir=none,style=invis];
2.133 + }
2.134 +
2.135 + subgraph {
2.136 + rank=same;
2.137 +
2.138 + PageQueue_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ndefinitively"];
2.139 + PageQueue [label="PageQueue"];
2.140 + Flexpage [shape=note];
2.141 + Pages [label="Pages"];
2.142 + Pages_note [shape=note,style=filled,fillcolor=gold,label="Claim and\nrecycle\nflexpage"];
2.143 +
2.144 + Flexpage_reserve [label="Flexpage",shape=note];
2.145 + Pages_reserve [label="Pages"];
2.146 + Pages_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage\nif available"];
2.147 +
2.148 + Pages_queue_note [shape=note,style=filled,fillcolor=gold,label="Queues\nissued\nflexpage"];
2.149 + Pages_queue [label="Pages"];
2.150 + Flexpage_queued [label="Flexpage",shape=note];
2.151 + PageQueue_queued [label="PageQueue"];
2.152 +
2.153 + PageQueue_note -> PageQueue [dir=none,style=dotted];
2.154 + Pages -> Pages_note [dir=none,style=dotted];
2.155 + Pages_reserve -> Pages_reserve_note [dir=none,style=dotted];
2.156 + Pages_queue_note -> Pages_queue [dir=none,style=dotted];
2.157 +
2.158 + Pages_note -> Flexpage_reserve [dir=none,style=invis];
2.159 + Pages_reserve_note -> Pages_queue_note [dir=none,style=invis];
2.160 + }
2.161 +
2.162 + subgraph {
2.163 + rank=same;
2.164 +
2.165 + Flexpage2 [label="Flexpage",shape=note];
2.166 + Flexpage2_note [shape=note,style=filled,fillcolor=gold,label="Reserved\nwhen obtained"];
2.167 +
2.168 + Flexpage2 -> Flexpage2_note [dir=none,style=dotted];
2.169 + }
2.170 +
2.171 + /* Second page mapper activities. */
2.172 +
2.173 + subgraph {
2.174 + rank=max;
2.175 +
2.176 + PageMapper2_note [shape=note,style=filled,fillcolor=gold,label="Obtain\nflexpage"];
2.177 + PageMapper2 [label="PageMapper"];
2.178 +
2.179 + PageMapper2_note -> PageMapper2 [dir=none,style=dotted];
2.180 + }
2.181 +
2.182 + /* First pager dataflow. */
2.183 +
2.184 + PageMapper1 -> AccessMap1 [label="find"];
2.185 + AccessMap1 -> Flexpage1 [dir=none];
2.186 + Flexpage1 -> PageMapper1;
2.187 +
2.188 + PageMapper1_reserve -> Flexpage1_reserve [dir=none];
2.189 + Flexpage1_reserve -> Pages_reserve [label="reserve"];
2.190 + Pages_reserve -> Flexpage1_reserved [dir=none];
2.191 + Flexpage1_reserved -> PageMapper1_reserve;
2.192 +
2.193 + PageMapper1_queue -> Flexpage1_queue [dir=none];
2.194 + Flexpage1_queue -> Pages_queue [label="queue"];
2.195 +
2.196 + /* Flexpage queuing. */
2.197 +
2.198 + Pages_queue -> Flexpage_queued [dir=none];
2.199 + Flexpage_queued -> PageQueue_queued;
2.200 +
2.201 + /* Flexpage retrieval from the queue. */
2.202 +
2.203 + Pages -> PageQueue [color="red"];
2.204 + PageQueue -> Flexpage [color="red",dir=none];
2.205 + Flexpage -> Pages [color="red"];
2.206 + Flexpage_reserve -> Pages_reserve;
2.207 +
2.208 + /* Flexpage removal from the access map. */
2.209 +
2.210 + Pages -> AccessMap1 [color="red",label="remove"];
2.211 +
2.212 + /* Second pager dataflow. */
2.213 +
2.214 + PageMapper2 -> Pages [color="red"];
2.215 + Pages -> Flexpage2 [color="red",dir=none];
2.216 + Flexpage2 -> PageMapper2 [color="red"];
2.217 +}
2.218 +}}}
2.219 +
2.220 +########