Within filesystem servers, a number of abstractions are combined to support access to filesystem content through paging: the delivery of content to clients in mapped memory.

  1. Overview
  2. Pagers and Files
  3. Obtaining and Queuing Pages
  4. Satisfying Requests for Pages
  5. Reclaiming and Recycling Pages
  6. Reserving Available Pages
  7. Queuing Issued Pages


The general mechanism used to support paging is depicted below.

pagingProvidesfilesystemcontentPagerPageMapperProvidespopulatedfile pagesAccessorAccessMapoffset-0flexpage-0...offset-nflexpage-n...PagesPopulatesfile pagesFlexpageoffsetsizeregionProvidesmemorypagesPageQueueowner-0flexpage-0...owner-Nflexpage-N...MemoryRegionAllocatesmemoryregions

A 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.

Pagers and Files

Each PageMapper is responsible for a particular file, and where multiple Pager objects provide access to a file for different clients, these will all share the same PageMapper and thus the same AccessMap and Accessor. The PageMapper is initialised when a Provider object is created to represent a file.

pagers_and_filesProvidesfilesystemcontentfor file #1PagerPagerPageMapperPagerProvidesfilesystemcontentfor file #2PageMapperProvidespopulatedfile pagesfor file #1AccessMapAccessorProvidespopulatedfile pagesfor file #2AccessMapManagesfile pagesfor file #1Managesfile pagesfor file #2Populatesfile pages

Obtaining and Queuing Pages

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.

Satisfying Requests for Pages

The general procedure for satisfying requests for pages is as follows:

  1. Attempt to find an existing page for the affected file region.
  2. With an existing page, attempt to reserve the page for issuing.
  3. Without an existing or reserved page, obtain a fresh page for populating.
  4. Queue the page for eventual reuse.

Since many files are likely to be in use, and since a fixed amount of memory may be shared to provide access to file content, the interaction between different PageMapper objects, operating on behalf of different files, must be taken into consideration. The following diagram depicts the principal mechanisms involved in securing access to pages so as to provide access to file content.

paging_concurrencyFindflexpagePageMapperAccessorflushAccessMapfindReserveflexpagePageMapperFlexpageQueueflexpagePageMapperFlexpageProvidesflexpagestentativelyflushFlexpageNeeds reservationif foundby mapperFlexpagePagesreserveClaimed ifstill availablePagesqueueProvidesflexpagesdefinitivelyPageQueueFlexpagePagesremove(via PageMapper)Reclaim andrecycleflexpageFlexpageProvidesreservedflexpagePageQueueFlexpageReserveflexpageif availableQueuesissuedflexpageFlexpagePageQueueFlexpagePageMapperReservedwhen obtainedAccessMapRecordsreservedflexpageFlexpagequeueObtainflexpageflexpageAccessorfillRecordflexpagePageMapperinsertQueueflexpagePageMapper

Reclaiming and Recycling Pages

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 employed by the PageMapper 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.

Reserving Available Pages

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.

Queuing Issued Pages

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.