Subject: Free Lists and Free Space Management
Modified: 28 Sep 94 04:04:20
This paper discussees the different kinds of free lists and the changes made
between V6.0 and 6.0.35/V7 in regard to space search algorithm. The paper has
been divided into the sections, abbreviations and definitions, block format
for segment headers, the differences in block format,
and space search algorithms.
Abbreviations and Definitions:
---------------------------------
Abbreviations:
V1 - V6.0 upto V6.0.34 inclusive
V2 - V6.0.35 upto Oracle7 inclusive
Txfl - Transaction Free list
Prfl - Process Free list
Sgfl - Segment Free list
Msfl - Master Free list
Infl - Instance Free list
Definitions:
Free list: Free list is a list of blocks which can be reused by that
segment. When deletes occur and the data in a block becomes less
than the specified pctused, this block is put on a free list.
Every time a block is added, it is added to the HEAD of the free
list. For example, Block B5 is on a free list called FL. It will
look like:
FL: B5
If another block B6 is added to the free list, the free list
will now look like this:
FL: B6-->B5
Which means the head of the free list is block B6 which points
to the next free block in the list which is B5. When a process
uses a block from the free list it uses B6 first.
Txfl: A free list allocated for every transaction. There are a
minimum of 16 Txfl per segment and it grows as needed until
the block is full. If a transaction needs a Txfl and if all
of them are allocated, it has to wait untill the next one is
available. All processes can access the Txfls for a given
instance when required.
Note that every transaction does not get allocated a Txfl
automatically. The only time it gets a transaction freelist is
if it is putting space back to the segment and if it does not
already have a Txfl allocated.
Prfl: A free list allocated for a process. A process will not search
the Prfl allocated to another process.
Sgfl: Synonym for Prfl.
Msfl: Introduced in v2. It is a preallocated Prfl which all processes
can access known as the Master free list. No such concept exists
in v1.
II. Block format for segment header in v1
-----------------------------------------
A segment consists of extents, which are a collection of contiguous blocks.
When a segment is created, the first block of the first extent is called the
segment header. The segment hearder contains:
1. Extent control
2. Extent map table
3. Segment header control
4. Segment Free space
5. Transaction Free space
The extent control and extent map table give information on the extents
allocated to the segment. The segment header control contains information
about the number of transaction free lists (nxf), the number of instance
lists (nfb) and the number of process free lists (nfl) that are specified
when the segment is created. Since we are talking about 6.0 through
6.0.34, the number of instance free lists (Infl) is 1 by default.
However if need this number to be higher than 1, then the number of Prfl is
calculated as:
Prfl/Sgfl = nfb * nfl
nfb is specified by the init.ora parameter FREE_LIST_INST
nfl is specified by the init.ora parameter FREE_LIST_PROC
NOTE: In v1, only the segment header has the information about all the free
lists. i.e. only one block was allocated to hold this information.
III. Differences in block format between v1 and v2
--------------------------------------------------
In V6.0.35 a new block type of 12 has been introduced for data segments
in addition to block type 5. So the segment header can be of type 5 or 12.
This is determined by looking at the number of free groups specified.
If the number of free groups is greater than 1, the block type for the
segment header will be set to 12.
In V6.0.35 and higher, we can specify information about free lists in the
storage clause.
....STORAGE (FREELISTS N
FREELIST GROUPS M)
The advantages are that freelists info can be stored in the data dictionary.
You don't need to shutdown and startup the database to change it like in v1.
Finally, this allows you to change free lists for one table, rather the entire
database.
The following table gives the comparision between 6.0 and 6.2/7.0
-----------------------------------------------------------------
|
6.0 and <= 6.0.34 | > 6.0.35 and 7.0
Block type always 5 | Block type = 5 if M=1
| Block type = 12 if M>1
|
--------------------------------|--------------------------------
|
FREE_LIST_INST (nfb) | M
|
FREE_LIST_PROC (nfl) | N
|
------------------------------------------------------------------
Another difference between v1 and v2 is that v1 had only one block allocated
for the freelists which was also the segment header. However, In v2, there
is one free list block for each free list group. For example, if M = 2,
then we have the segment header, and the next two blocks are allocated, one
for each free list group.
In other words, all processes will be mapped to one free list block. The
thread number is used to assign one instance to one free list block. Another
alternative is to specify the init.ora parameter INSTANCE_NUMBER. If N>1,
one of the Prfl is reserved and called the Master freelist.
IV. Mapping function and free space search algorithm.
-----------------------------------------------------
Mapping function:
The mapping function takes the thread control in the redo log that the
instance is using and maps it to the free list group. It then takes the
process number and maps it to the process free list within that group.
The mapping fuction is simply the thread number % freelist groups and process
number % process freelists.
For example, let M = 3 and N = 5 this means there are 3 free list groups
each having 5 process free lists, as illustrated in the following diagram:
1 (1 2 3 4 5) 2 ( 1 2 3 4 5) 3 ( 1 2 3 4 5)
Now lets assume a process is connected to instance 2. Which freelist
will it be allocated to? Lets assume that the thread number is 10 and
the process number is 26.
Then 10 % 3 = 1
26 % 5 = 1
So it will take the first Prfl of the first group.
If you want to force oracle to assign an instance a specific
freelist block, use the init.ora parameter INSTANCE_NUMBER
Search algorithm:
In version 6.0.34 and lower, we follow the following steps:
1. Search for free space on its own transaction free list (Trfl)
If found goto 7 else goto step 2.
2. Search for free space on the process freelist. If found goto 7.
If not found goto step 3.
3. Search for committed Txfls. If no committed Txfl space found,
goto step 4.
Else:
Assign each committed Txfl space to one Prfl.
If Prfl > Trfl, some Prfl do not get space.
If Prfl < Trfl, some Prfl get more space.
goto step 2.
4. Can High Water Mark be bumped up? If no, goto step 5.
If yes, bump up by some number and copy space to Prfl and goto 2.
5. Go to data dict. Search fet$ and allocate an extent to segment
and goto step 4. If no space in fet$ goto step 6.
6. Error. No more space in tablespace.
7. Use the space.
In version 6.0.35 and higher, we follow the following steps:
1. Search for free space on its own transaction free list (Trfl)
If found goto step 8 else goto step 2.
2. Search for free space on the process freelist. If found goto step 8.
If not found goto step 3.
3. Search Master freelist. If space found copy a chunk of it
to Prfl and goto step 2 else goto step 4.
4. Search for committed Txfls. If no committed Txfl space found,
goto step 5.
Else:
Copy space from the first committed Txfl to
Master freelist
goto step 3.
5. Can High Water Mark be bumped up? If no, goto step 6
If yes, bump up by some number and copy space to Prfl and goto 2.
6. Go to data dict. Search fet$ and allocate an extent to segment
and goto 4. If no space in fet$ goto 7.
7. Error. No more space in tablespace.
8. Use the space.