Bitmap Caches

When the kernel mounts an Ext2 filesystem, it allocates a buffer for the Ext2 disk superblock and reads its contents from disk. The buffer is released only when the Ext2 filesystem is unmounted. When the kernel must modify a field in the Ext2 superblock, it simply writes the new value in the proper position of the corresponding buffer and then marks the buffer as dirty.

Unfortunately, this approach cannot be adopted for all Ext2 disk data structures. The tenfold increase in disk capacity reached in recent years has induced a tenfold increase in the size of inode and data block bitmaps, so we have reached the point at which it is no longer convenient to keep all the bitmaps in RAM at the same time.

For instance, consider a 4-GB disk with a 1-KB block size. Since each bitmap fills all the bits of a single block, each of them describes the status of 8,192 blocks — that is, of 8 MB of disk storage. The number of block groups is 4,096 MB/8 MB=512. Since each block group requires both an inode bitmap and a data block bitmap, 1 MB of RAM would be required to store all 1,024 bitmaps in memory.

The solution adopted to limit the memory requirements of the Ext2 descriptors is to use, for any mounted Ext2 filesystem, two caches of size ext2_max_group_loaded (usually 8).

One cache stores the most recently accessed inode bitmaps, while the other cache stores the most recently accessed block bitmaps. Buffers that contain bitmaps included in a cache have a usage counter greater than 0, therefore they are never freed by shrink_mmap( ) (see Section 16.7). Conversely, buffers that contain bitmaps not included in a bitmap cache have a null usage counter, so they can be freed if free memory becomes scarce.

Each cache is implemented by means of two arrays of ext2_max_group_loaded elements.

One array contains the indexes of the block groups whose bitmaps are currently in the cache, while the other array contains pointers to the buffer heads that refer to those bitmaps.

The ext2_sb_info structure stores the arrays pertaining to the inode bitmap cache; indexes of block groups are found in the s_inode_bitmap field and pointers to buffer heads are found in the s_inode_bitmap_number field. The corresponding arrays for the block bitmap cache are stored in the s_block_bitmap and s_block_bitmapnumber fields.

The load_inode_bitmap( ) function loads the inode bitmap of a specified block group and returns the cache position in which the bitmap can be found.

If the bitmap is not already in the bitmap cache, load_inode_bitmap( ) invokes read_inode_bitmap( ). The latter function gets the number of the block containing the bitmap from the bg_inode_bitmap field of the group descriptor, and then invokes bread( ) to allocate a new buffer and read the block from disk if it is not already included in the buffer cache.

If the number of block groups in the Ext2 partition is less than or equal to ext2_max_group_loaded, the index of the cache array position in which the bitmap is inserted always matches the block group index passed as the parameter to the load inode bitmap( ) function.

Otherwise, if there are more block groups than cache positions, a bitmap is removed from the cache, if necessary, by using a Least Recently Used (LRU) policy, and the requested bitmap is inserted in the first cache position. Figure 17-3 illustrates the three possible cases in which the bitmap in block group 5 is referenced: where the requested bitmap is already in cache, where the bitmap is not in cache but there is a free position, and where the bitmap is not in cache and there is no free position.

Figure 17-3. Adding a bitmap to the cache

Birmjj^ rttdyin tache

3

1

17

A

El

J

6

20

(b) Birnnap added to Theatre

3

1

17

A

S

Ul Biiriijj èdd?d u ihe tithe. Un Wimap thrawi Dui

3

1

17

i

S

6

20

7

3

1

17

■1

«

6

¿0

5

3

1

17

■1

3

S

3

1

17

■1

3

6

20

The load_block_bitmap( ) and read_block_bitmap( ) functions are very similar to load_inode_bitmap( ) and read_inode_bitmap( ) , but they refer to the block bitmap cache of an Ext2 partition.

Figure 17-4 illustrates the memory data structures of a mounted Ext2 filesystem. In our example, there are three block groups whose descriptors are stored in three blocks on disk; therefore, the s_group_desc field of the ext2_sb_info points to an array of three buffer heads. We have shown just one inode bitmap having index 2 and one block bitmap having index 4, although the kernel may keep 2 x ext2_max_group_loaded bitmaps in the bitmap caches, and even more may be stored in the buffer cache.

Figure 17-4. Ext2 memory data structures

Figure 17-4. Ext2 memory data structures

Ext2 Bitmap

Was this article helpful?

+1 0

Post a comment