Skip to content

free_space.py

ofrak.core.free_space

Allocatable (ResourceView) dataclass

Identifies a resource that may have some free space available within it to allocate (for arbitrary purposes). Once tagged as an Allocatable, a resource may be analyzed to find all of the available free space within it and its descendants. These ranges are stored as minimal lists of contiguous ranges of free space (ranges which overlap or touch are combined), sorted first by size then vaddr (lowest to highest). Each list of free space ranges contains only free space with one type of memory access permissions of the ranges, i.e. all read-only free space is stored in one list, all read-execute free-space is stored in another list, etc.

allocate(self, permissions, requested_size, alignment=4, min_fragment_size=None, within_range=None) async

Request some range(s) of free space which satisfies the given constraints as parameters. If such ranges are found, the resources they belong to (which are descendants of this Allocatable) are modified to reflect that part or all of them are no longer valid free space using RemoveFreeSpaceModifier.

Allows either a fragmented allocation (X space is allocated across N individual ranges), or a non-fragmented allocation (one range of size X). To force the allocation to be non-fragmented, set the min_fragment_size param equal to the requested_size.

Parameters:

Name Type Description Default
permissions MemoryPermissions

Required memory permissions of the free space (exact match)

required
requested_size int

Total size of allocated ranges

required
alignment int

That start of the allocated ranges will be aligned to alignment bytes

4
min_fragment_size Optional[int]

The minimum size of each allocated range

None
within_range Optional[ofrak_type.range.Range]

All returned ranges must be within this virtual address range

None

Returns:

Type Description
List[ofrak_type.range.Range]

A list of one or more Range, which each contain a start and end vaddr of an allocated range of free space

Exceptions:

Type Description
FreeSpaceAllocationError

if there is not enough free space to allocate which matches the given constraints

Source code in ofrak/core/free_space.py
async def allocate(
    self,
    permissions: MemoryPermissions,
    requested_size: int,
    alignment: int = 4,
    min_fragment_size: Optional[int] = None,
    within_range: Optional[Range] = None,
) -> List[Range]:
    """
    Request some range(s) of free space which satisfies the given constraints as parameters.
    If such ranges are found, the resources they belong to (which are descendants of this
    `Allocatable`) are modified to reflect that part or all of them are no longer valid free
    space using
    [RemoveFreeSpaceModifier][ofrak.core.free_space.RemoveFreeSpaceModifier].

    Allows either a fragmented allocation (X space is allocated across N individual ranges),
    or a non-fragmented allocation (one range of size X). To force the allocation to be
    non-fragmented, set the `min_fragment_size` param equal to the `requested_size`.

    :param permissions: Required memory permissions of the free space (exact match)
    :param requested_size: Total size of allocated ranges
    :param alignment: That start of the allocated ranges will be aligned to `alignment` bytes
    :param min_fragment_size: The minimum size of each allocated range
    :param within_range: All returned ranges must be within this virtual address range

    :return: A list of one or more [Range][ofrak_type.range.Range], which each contain a
     start and end vaddr of an allocated range of free space

    :raises FreeSpaceAllocationError: if there is not enough free space to allocate which
    matches the given constraints
    """
    allocated_ranges = await self._allocate(
        permissions,
        requested_size,
        alignment,
        min_fragment_size,
        within_range,
    )

    # Having acquired a satisfactory allocation, make sure subsequent calls won't allocate
    # from this same block
    await self.resource.run(
        RemoveFreeSpaceModifier,
        FreeSpaceAllocation(
            permissions,
            allocated_ranges,
        ),
    )
    self.remove_allocation_from_cached_free_ranges(allocated_ranges, permissions)

    return allocated_ranges

FreeSpace (MemoryRegion) dataclass

FreeSpace(virtual_address: int, size: int, permissions: ofrak_type.memory_permissions.MemoryPermissions)

FreeSpaceAllocation (ComponentConfig) dataclass

FreeSpaceAllocation(permissions: ofrak_type.memory_permissions.MemoryPermissions, allocations: List[ofrak_type.range.Range])

FreeSpaceAnalyzer (Analyzer)

Analyze an Allocatable resource to find the ranges of free space it contains by searching for descendants tagged as FreeSpace. The ranges of each individual FreeSpace resource will be globbed into as few non-overlapping ranges as possible. The ranges of different types of free space - such as RW permissions vs RX permissions - will be calculated and stored separately.

analyze(self, resource, config) async

Analyze a resource for to extract specific ResourceAttributes.

Users should not call this method directly; rather, they should run Resource.run or Resource.analyze.

Parameters:

Name Type Description Default
resource Resource

The resource that is being analyzed

required
config None

Optional config for analyzing. If an implementation provides a default, this default will always be used when config would otherwise be None. Note that a copy of the default config will be passed, so the default config values cannot be modified persistently by a component run.

required

Returns:

Type Description
Allocatable

The analysis results

Source code in ofrak/core/free_space.py
async def analyze(self, resource: Resource, config: None) -> Allocatable:
    ranges_by_permissions = defaultdict(list)
    for free_space_r in await resource.get_descendants_as_view(
        FreeSpace,
        r_filter=ResourceFilter.with_tags(FreeSpace),
        r_sort=ResourceSort(FreeSpace.VirtualAddress),
    ):
        ranges_by_permissions[free_space_r.permissions].append(free_space_r.vaddr_range())

    merged_ranges_by_permissions = dict()
    for perms, ranges in ranges_by_permissions.items():
        merged_ranges_by_permissions[perms] = Allocatable.sort_free_ranges(
            Range.merge_ranges(ranges)
        )

    return Allocatable(merged_ranges_by_permissions)

FreeSpaceModifier (Modifier)

Turn a MemoryRegion resource into allocatable free space by replacing its data with b'' or optionally specified bytes. FreeSpace.

modify(self, resource, config) async

Modify the given resource.

Users should not call this method directly; rather, they should run Resource.run.

Parameters:

Name Type Description Default
resource Resource required
config FreeSpaceModifierConfig

Optional config for modification. If an implementation provides a default, this default will always be used when config would otherwise be None. Note that a copy of the default config will be passed, so the default config values cannot be modified persistently by a component run.

required
Source code in ofrak/core/free_space.py
async def modify(self, resource: Resource, config: FreeSpaceModifierConfig):
    mem_region_view = await resource.view_as(MemoryRegion)

    freed_range = Range(
        mem_region_view.virtual_address,
        mem_region_view.virtual_address + mem_region_view.size,
    )
    patch_data = _get_fill(freed_range, config.fill)
    parent_mr_view = await resource.get_parent_as_view(MemoryRegion)
    patch_offset = parent_mr_view.get_offset_in_self(freed_range.start)
    patch_range = freed_range.translate(patch_offset - freed_range.start)

    await resource.delete()
    await resource.save()

    await parent_mr_view.resource.create_child_from_view(
        FreeSpace(
            mem_region_view.virtual_address,
            mem_region_view.size,
            config.permissions,
        ),
        data_range=patch_range,
        data=patch_data,
    )

FreeSpaceModifierConfig (ComponentConfig) dataclass

Configuration for modifier which marks some free space.

Attributes:

Name Type Description
permissions MemoryPermissions

memory permissions to give the created free space.

fill Optional[bytes]

bytes to fill the free space with

PartialFreeSpaceModifier (Modifier)

Turn part of a MemoryRegion resource into allocatable free space by replacing a range of its data with b'' or optionally specified fill bytes. FreeSpace child resource at that range.

modify(self, resource, config) async

Modify the given resource.

Users should not call this method directly; rather, they should run Resource.run.

Parameters:

Name Type Description Default
resource Resource required
config PartialFreeSpaceModifierConfig

Optional config for modification. If an implementation provides a default, this default will always be used when config would otherwise be None. Note that a copy of the default config will be passed, so the default config values cannot be modified persistently by a component run.

required
Source code in ofrak/core/free_space.py
async def modify(self, resource: Resource, config: PartialFreeSpaceModifierConfig):
    mem_region_view = await resource.view_as(MemoryRegion)
    freed_range = config.range_to_remove
    patch_data = _get_fill(freed_range, config.fill)
    virtual_patch_range = Range.intersect(
        Range(mem_region_view.virtual_address, mem_region_view.end_vaddr()), freed_range
    )
    await _find_and_delete_overlapping_children(resource, freed_range)
    patch_offset = mem_region_view.get_offset_in_self(virtual_patch_range.start)
    patch_range = Range.from_size(patch_offset, virtual_patch_range.length())

    await mem_region_view.resource.create_child_from_view(
        FreeSpace(
            virtual_patch_range.start,
            virtual_patch_range.length(),
            config.permissions,
        ),
        data_range=patch_range,
        data=patch_data,
    )

PartialFreeSpaceModifierConfig (ComponentConfig) dataclass

Attributes:

Name Type Description
permissions MemoryPermissions

memory permissions to give the created free space.

range_to_remove Range

the ranges to consider as free space (remove)

fill Optional[bytes]

bytes to fill the free space with

RemoveFreeSpaceModifier (Modifier)

After allocating some space from an Allocatable, fix up its descendants to make sure the allocated space will not be allocated again. Remove FreeSpace tags from resources which overlap with an allocated range. If part of one of these resources is not within an allocated range, create a child tagged as FreeSpace to reflect that part of it is still available as free space.

modify(self, resource, config) async

Modify the given resource.

Users should not call this method directly; rather, they should run Resource.run.

Parameters:

Name Type Description Default
resource Resource required
config FreeSpaceAllocation

Optional config for modification. If an implementation provides a default, this default will always be used when config would otherwise be None. Note that a copy of the default config will be passed, so the default config values cannot be modified persistently by a component run.

required
Source code in ofrak/core/free_space.py
async def modify(self, resource: Resource, config: FreeSpaceAllocation) -> None:

    wholly_allocated_resources = list()
    partially_allocated_resources: Dict[bytes, Tuple[FreeSpace, List[Range]]] = dict()
    allocatable = await resource.view_as(Allocatable)

    for alloc in config.allocations:
        for res_wholly_in_alloc in await resource.get_descendants_as_view(
            FreeSpace,
            r_filter=ResourceFilter(
                tags=(FreeSpace,),
                attribute_filters=(
                    ResourceAttributeValueFilter(
                        FreeSpace.Permissions, config.permissions.value
                    ),
                    ResourceAttributeRangeFilter(
                        FreeSpace.VirtualAddress,
                        min=alloc.start,
                        max=alloc.end - 1,
                    ),
                    ResourceAttributeRangeFilter(
                        FreeSpace.EndVaddr, min=alloc.start + 1, max=alloc.end
                    ),
                ),
            ),
        ):
            wholly_allocated_resources.append(res_wholly_in_alloc)

        for res_partially_in_alloc in await self._get_partially_overlapping_resources(
            resource,
            config.permissions,
            alloc,
        ):
            free_space_range = res_partially_in_alloc.vaddr_range()
            overlap = alloc.intersect(free_space_range)
            assert overlap.length() > 0
            free_space_res_id = res_partially_in_alloc.resource.get_id()
            if free_space_res_id in partially_allocated_resources:
                _, allocated_ranges_of_res = partially_allocated_resources[free_space_res_id]
                allocated_ranges_of_res.append(overlap)
            else:
                partially_allocated_resources[free_space_res_id] = (
                    res_partially_in_alloc,
                    [overlap],
                )

    for fs in wholly_allocated_resources:
        fs.resource.remove_tag(FreeSpace)

    for fs, allocated_ranges in partially_allocated_resources.values():
        remaining_free_space_ranges = remove_subranges([fs.vaddr_range()], allocated_ranges)
        for remaining_range in remaining_free_space_ranges:
            remaining_data_range = Range.from_size(
                fs.get_offset_in_self(remaining_range.start), remaining_range.length()
            )
            await fs.resource.create_child_from_view(
                FreeSpace(
                    remaining_range.start,
                    remaining_range.length(),
                    fs.permissions,
                ),
                data_range=remaining_data_range,
            )
        fs.resource.remove_tag(FreeSpace)

    # Update Allocatable attributes, reflecting removed ranges
    allocatable.remove_allocation_from_cached_free_ranges(
        config.allocations, config.permissions
    )
    resource.add_view(allocatable)