Home » Blog » The Global Allocation Map (GAM)

The Global Allocation Map (GAM)

2014-04-16 - General, Series, SQL Server Internals, Storage Wednesday

Introduction

SQL Server uses a structure called the Global Allocation Map (GAM) to keep track of all free extents in a database file. The GAM is consists of several GAM pages, one for each GAM Interval in each file.

GAM Pages

The GAM page is the first page of each GAM interval, with the exception of the first GAM page in a file. The first GAM page is always located on the third page, as page 0 and page 1 are reserved for other usages. As a GAM interval is 511232 pages that means, that you can find the GAM pages at page 3, 511232, 1022464, 1533696 and so on.

A GAM page is indicated by page type 8. The header of a GAM page looks like this:

One thing to note is the slot count of two. All extent-state tracking pages (IAM, GAM, SGAM, DIFF, ML) are setup the same way. At the beginning, there is an array that can be used to store eight page ids. IAM pages use that to track pages in mixed extents. However, that array is not used in the other page types. Following that array is an area of 7988 bytes used to track the state of 63904 extents, which is incidentally the size of a GAM interval. At the end of the page, you have the slot array, which points to the beginning of those two sections. Therefore, a page of any of those five page types always ends in 0xbe006000.

Each extent in a GAM interval is associated with a single bit in the GAM page for that same GAM interval. That bit is used to track if the extent is in use or not. If the extent is currently unused, the bit is set to 1. If the extent is a uniform extent and has been allocated to a table, the bit is set to 0. If the extent is a mixed extent, the bit is also set to 0, even though there might be still pages unused and available in that extent.

A bit valued 1 therefore means, this extent is available to be allocated to any type of use, whereas a 0 means that this extent is in use already.

Below is the (shortened) output of DBCC PAGE(0,1,2,2); for one of my databases:

[sourcecode] PAGE: (1:2)

BUFFER:

BUF @0x000000000400C240

bpage = 0x00000001F4F06000 bhash = 0x0000000000000000 bpageno = (1:2)
bdbid = 21 breferences = 1 bcputicks = 0
bsampleCount = 0 bUse1 = 35183 bstat = 0x10b
blog = 0x2121215a bnext = 0x0000000000000000

PAGE HEADER:

Page @0x00000001F4F06000

m_pageId = (1:2) m_headerVersion = 1 m_type = 8
m_typeFlagBits = 0x0 m_level = 0 m_flagBits = 0x0
m_objId (AllocUnitId.idObj) = 99 m_indexId (AllocUnitId.idInd) = 0 Metadata: AllocUnitId = 6488064
Metadata: PartitionId = 0 Metadata: IndexId = 0 Metadata: ObjectId = 99
m_prevPage = (0:0) m_nextPage = (0:0) pminlen = 90
m_slotCnt = 2 m_freeCnt = 6 m_freeData = 8182
m_reservedCnt = 0 m_lsn = (40361:723:7) m_xactReserved = 0
m_xdesId = (0:0) m_ghostRecCnt = 0 m_tornBits = -1158090570
DB Frag ID = 1

Allocation Status

GAM (1:2) = ALLOCATED SGAM (1:3) = NOT ALLOCATED PFS (1:1) = 0x44 ALLOCATED 100_PCT_FULL
DIFF (1:6) = CHANGED ML (1:7) = NOT MIN_LOGGED

DATA:

Memory Dump @0x000000006F70A000

000000006F70A000: 01080000 00000000 00000000 00005a00 00000000 ..............Z.....
000000006F70A014: 00000200 63000000 0600f61f 02000000 01000000 ....c.....ö.........
000000006F70A028: a99d0000 d3020000 07000000 00000000 00000000 ©...Ó...............
000000006F70A03C: b6f0f8ba 01000000 00000000 00000000 00000000 ¶ðøº................
000000006F70A050: 00000000 00000000 00000000 00000000 00005e00 ..................^.
000000006F70A064: 00000000 00000000 00000000 00000000 00000000 ....................
000000006F70A078: 00000000 00000000 00000000 00000000 00000000 ....................
000000006F70A08C: 00000000 00000000 00000000 00000000 00000000 ....................
000000006F70A0A0: 00000000 00000000 00000000 00000000 00000000 ....................
000000006F70A0B4: 00000000 00000000 00000000 381f0000 0000c0ff ............8.....Àÿ
000000006F70A0C8: ffffffff ffffffff ffffffff ffffffff ffffffff ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ
<...>
000000006F70BFE0: ffffffff ffffffff ffffffff ffffffff ffffffff ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ
000000006F70BFF4: ffff0000 00000000 be006000 ÿÿ......¾.`.

DBCC execution completed. If DBCC printed error messages, contact your system administrator.
[/sourcecode]

The slot array tells us the (unused) array of eight pages starts at byte 0x60, followed by the bit map at byte 0xbe. At position 0xbe you find the value 0x0000381f. That value is the length of the bitmap. As that length is always the same, you will find that same value at that exact position in all extent-state bitmap pages.

Directly after that length value the actual bitmap starts. In the example above you see four 0x00 byte, followed by a single 0xc0. The rest of the map is filled with 0xff bytes. The first 4 bytes indicate that the first 32 extents (pages 0 to 255) are in use. The byte 0xc0 adds another 6 extents or 48 pages to that. That means that the first free extent in this file starts at page 304. If you use output type 3 with DBCC PAGE for this GAM page (DBCC PAGE(0,1,2,3);), you can quickly confirm that calculation:

[sourcecode] GAM: Extent Alloc Status @0x000000006AFEA0C2

(1:0) - (1:296) = ALLOCATED
(1:304) - (1:511224) = NOT ALLOCATED
[/sourcecode]

Summary

GAM pages are used by SQL Server to track, which extents are in use and which ones are unallocated. Each GAM page contains a 7988-byte bitmap covering all extent in a single GAM interval of 511232 pages. Each bit corresponds to a single extent, and a value of 1 indicates that that extent is still unallocated.