Example of next_fit algorithm showing behavior of full regions, selectors, and priority

The input section properties and ordering are shown in the following table:

The scatter file used for the examples is:

LR 0x100
{
  ER_1 0x100 0x20
  {
     .ANY1(+RO-CODE)
  }
  ER_2 0x200 0x20
  {
     .ANY2(+RO)
  }
  ER_3 0x300 0x20
  {
     .ANY3(+RO)
  }
}

The next_fit algorithm is different to the others in that it never revisits a region that is considered to be full. This example also shows the interaction between priority and specificity of selectors. This is the same for all the algorithms.

    Execution Region ER_1 (Base: 0x00000100, Size: 0x00000014, Max: 0x00000020, ABSOLUTE)

    Base Addr    Size         Type   Attr      Idx    E Section Name        Object

    0x00000100   0x00000014   Code   RO            1    sec1                sections.o


    Execution Region ER_2 (Base: 0x00000200, Size: 0x0000001c, Max: 0x00000020, ABSOLUTE)

    Base Addr    Size         Type   Attr      Idx    E Section Name        Object

    0x00000200   0x00000010   Code   RO            3    sec3                sections.o
    0x00000210   0x00000004   Code   RO            4    sec4                sections.o
    0x00000214   0x00000004   Code   RO            5    sec5                sections.o
    0x00000218   0x00000004   Code   RO            6    sec6                sections.o


    Execution Region ER_3 (Base: 0x00000300, Size: 0x00000014, Max: 0x00000020, ABSOLUTE)

    Base Addr    Size         Type   Attr      Idx    E Section Name        Object

    0x00000300   0x00000014   Code   RO            2    sec2                sections.o

In this example:

• The linker places sec1 in ER_1 because ER_1 has the most specific selector. ER_1 now has 0x6 bytes remaining.
• The linker then tries to place sec2 in ER_1, because it has the most specific selector, but there is not enough space. Therefore, ER_1 is marked as full and is not considered in subsequent placement steps. The linker chooses ER_3 for sec2 because it has higher priority than ER_2.
• The linker then tries to place sec3 in ER_3. It does not fit, so ER_3 is marked as full and the linker places sec3 in ER_2.
• The linker now processes sec4. This is 0x4 bytes so it can fit in either ER_1 or ER_3. Because both of these sections have previously been marked as full, they are not considered. The linker places all remaining sections in ER_2.
• If another section sec7 of size 0x8 exists, and is processed after sec6 the example fails to link. The algorithm does not attempt to place the section in ER_1 or ER_3 because they have previously been marked as full.