Cache Data Structures

The cache manager uses the following data structures to keep track of cached files:

• Each 256-KB slot in the system cache is described by a VACB.

• Each separately opened cached file has a private cache map, which contains information used to control read-ahead (discussed later in the chapter).

• Each cached file has a single shared cache map structure, which points to slots in the system cache that contain mapped views of the file.

These structures and their relationships are described in the next sections.

Systemwide Cache Data Structures

The cache manager keeps track of the state of the views in the system cache by using an array of data structures called virtual address control blocks (VACBs). During system initialization, the cache manager allocates a single chunk of nonpaged pool to contain all the VACBs required to describe the system cache. It stores the address of the VACB array in the variable CcVacbs. Each VACB represents one 256-KB view in the system cache, as shown in Figure 11-8. The structure of a VACB is shown in Figure 11-9.

Figure 11-8. System VACB array

Figure 11-9. VACB structure

As you can see in Figure 11-9, the first field in a VACB is the virtual address of the data in the system cache. The second field is a pointer to the shared cache map structure, which identifies which file is cached. The third field identifies the offset within the file at which the view begins (always based on a 256-KB granularity). Finally, the VACB contains the number of references to the view that is, how many active reads or writes are accessing the view. During an I/O operation on a file, the file's VACB reference count is incremented and then it's decremented when the I/O operation is over. When the reference count is non-zero the VACB is active. For access to file system metadata, the active count represents how many file system drivers have the pages in that view locked into memory.

Per-File Cache Data Structures

Each open handle to a file has a corresponding file object. (File objects are explained in detail in Chapter 9.) If the file is cached, the file object points to a private cache map structure that contains the location of the last two reads so that the cache manager can perform intelligent read-ahead (described in the section "Intelligent Read-Ahead"). In addition, all the private cache maps for open instances of a file are linked together.

Each cached file (as opposed to file object) has a shared cache map structure that describes the state of the cached file, including its size and (for security reasons) its valid data length. (The function of the valid data length field is explained in the section "Write-Back Caching and Lazy Writing".) The shared cache map also points to the section object (maintained by the memory manager, and which describes the file's mapping into virtual memory), the list of private cache maps associated with that file, and any VACBs that describe currently mapped views of the file in the system cache. (See Chapter 7 for more about section object pointers.) The relationships among these per-file cache data structures are illustrated in Figure 11-10.

Figure 11-10. Per-file cache data structures

When asked to read from a particular file, the cache manager must determine the answers to two questions:

1. Is the file in the cache?

2. If so, which VACB, if any, refers to the requested location?

In other words, the cache manager must find out whether a view of the file at the desired address is mapped into the system cache. If no VACB contains the desired file offset, the requested data isn't currently mapped into the system cache.

To keep track of which views for a given file are mapped into the system cache, the cache manager maintains an array of pointers to VACBs, which is known as the VACB index array. The first entry in the VACB index array refers to the first 256 KB of the file, the second entry to the second 256 KB, and so on. The diagram in Figure 11-11 shows four different sections from three different files that are currently mapped into the system cache.

Figure 11-11. VACB index arrays

When a process accesses a particular file in a given location, the cache manager looks in the appropriate entry in the file's VACB index array to see whether the requested data has been mapped into the cache. If the array entry is nonzero (and hence contains a pointer to a VACB), the area of the file being referenced is in the cache. The VACB, in turn, points to the location in the system cache where the view of the file is mapped. If the entry is zero, the cache manager must find a free slot in the system cache (and therefore a free VACB) to map the required view.

As a size optimization, the shared cache map contains a VACB index array that is 4 entries in size. Because each VACB describes 256 KB, the entries in this small fixed-size index array can point to VACB array entries that together describe a file of up to 1 MB. If a file is larger than 1 MB, a separate VACB index array is allocated from nonpaged pool, based on the size of the file divided by 256 KB and rounded up in the case of a remainder. The shared cache map then points to this separate structure.

As a further optimization, the VACB index array allocated from nonpaged pool becomes a sparse multilevel index array if the file is larger than 32 MB, where each index array consists of 128 entries. You can calculate the number of levels required for a file with the following formula:

(Number of bits required to represent file size - 18) / 7

Round the result of the equation up to the next whole number. The value 18 in the equation comes from the fact that a VACB represents 256 KB, and 256 KB is 2¹⁸. The value 7 comes from the fact that each level in the array has 128 entries and 2⁷is 128. Thus, a file that has a size that is the maximum that can be described with 63 bits (the largest size the cache manager supports) would require only seven levels. The array is sparse because the only branches that the cache manager allocates are ones for which there are active views at the lowest-level index array. Figure 11-12 shows an example of a multilevel VACB array for a sparse file that is large enough to require three levels.

Figure 11-12. Multilevel VACB arrays

This scheme is required to efficiently handle sparse files that might have extremely large file sizes with only a small fraction of valid data because only enough of the array is allocated to handle the currently mapped views of a file. For example, a 32-GB sparse file for which only 256 KB is mapped into the cache's virtual address space would require a VACB array with three allocated index arrays because only one branch of the array has a mapping and a 32-GB (2³⁵bytes) file requires a three-level array. If the cache manager didn't use the multilevel VACB array optimization for this file, it would have to allocate a VACB array with 128,000 entries, or the equivalent of 1000 index arrays.

EXPERIMENT: Looking at Shared and Private Cache Maps

You can use the kernel debugger's dt command to look at the shared and private cache map data structure definitions and examine the structures on a live system. First, execute the !filecache command and locate an entry in the VACB output with a file name you recognize. In this example, the file is a Microsoft Outlook data file:

8653c828  120  160   0   0 debugger.chm

The first address is that of a control area data structure, which the memory manager uses to keep track of an address range. (See Chapter 7 for more information.) The control area stores the pointer to the file object that corresponds to the view in the cache. A file object identifies an instance of an open file, in this example the Debugging Tools for Windows help file. Execute the following command using the address of the control area of the entry you identified to see the control area structure:

lkd> !ca 8653c828 ControlArea    @8653c828   Segment:       e1bce428    Flink           0  Blink             0   SectionRef            1    Pfn Ref        46  MappedViews       4   UserRef               0    WaitForDel      0  Flush Count       0   FileObject85d927a8         ModWriteCount   0  SystemViews       0   Flags  (8008080)File  WasPurged  Accessed   File:  \ProgramFiles\Debugging  Toolsfor  Windows\debugger.chm

Next look at the file object referenced by the control area with this command:

lkd> dt _File_object 85d927a8 nt!_FILE_OBJECT    +0x000Type             : 5    +0x002Size             : 112    +0x004DeviceObject     : 0x86b78e30    +0x008Vpb              : 0x86b90d80    +0x00cFsContext        : 0xe3b629e0    +0x010FsContext2       : 0xe3b62b38    +0x014SectionObjectPointer: 0x85e7a334    +0x018PrivateCacheMap  : 0x862f5a50    +0x01cFinalStatus      :  0    +0x020RelatedFileObject : (null)    +0x024LockOperation    :  0'' ...

The private cache map is at offset 0x18:

lkd>dt  _private_cache_map0x862f5a50 nt!_PRIVATE_CACHE_MAP    +0x000NodeTypeCode       : 766    +0x000Flags              : _PRIVATE_CACHE_MAP_FLAGS    +0x000UlongFlags         : 0x2fe    +0x004ReadAheadMask      : 0xffff    +0x008FileObject         : 0x85d927a8    +0x010FileOffset1        : _LARGE_INTEGER 0x10b28    +0x018BeyondLastByte1    : _LARGE_INTEGER 0x12206    +0x020FileOffset2        : _LARGE_INTEGER 0x10b28    +0x028BeyondLastByte2    : _LARGE_INTEGER 0x12206    +0x030ReadAheadOffset    : [2]   _LARGE_INTEGER0x0    +0x040ReadAheadLength    : [2] 0    +0x048ReadAheadSpinLock  : 0    +0x04cPrivateLinks      : _LIST_ENTRY  [  0x862f5a10 - 0x862f5a10]

Finally, you can locate the shared cache map in the SectionObjectPointers structure of the file object and then view its contents:

lkd> dt _Section_object_pointers 0x85e7a334 nt!_SECTION_OBJECT_POINTERS    +0x000DataSectionObject : 0x8653c828    +0x004SharedCacheMap : 0x862f5978    +0x008ImageSectionObject : (null) lkd> dt _shared_cache_map 0x862f5978 nt!_SHARED_CACHE_MAP    +0x000NodeTypeCode         : 767    +0x002NodeByteSize         : 304    +0x004OpenCount            : 1    +0x008FileSize             : _LARGE_INTEGER  0x19970a    +0x010BcbList              : _LIST_ENTRY  [ 0x862f5988 -  0x862f5988 ]    +0x018SectionSize          : _LARGE_INTEGER  0x1c0000    +0x020ValidDataLength      : _LARGE_INTEGER  0x19970a    +0x028ValidDataGoal        : _LARGE_INTEGER  0x19970a    +0x030InitialVacbs         : [4]  (null)    +0x040Vacbs                : 0x85d42c00  -> 0x86bba610    +0x044FileObject           : 0x85d927a8    +0x048ActiveVacb           : 0x86bba610 ...