ARM Compiler toolchain v4.1 for µVision Using the Linker: Example of next_fit algorithm showing behavior of full regions, selectors, and priority

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

This example shows the operation of the next_fit placement algorithm for RO-CODE sections in sections.o.

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

Table 11. Input section properties

Name	Size
`sec1`	`0x4`
`sec2`	`0x4`
`sec3`	`0x4`
`sec4`	`0x4`
`sec5`	`0x4`
`sec6`	`0x4`

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)
  }
}

Note

This example has --any_contingency disabled.

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.

Copyright © 2007-2008, 2011 ARM. All rights reserved.	ARM DUI 0377C
Non-Confidential	ID061811
PDF version

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

Note

See also

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