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

`allocate_bom(self, bom, permission_map=None)` `async`

Responsible for allocating the patches if free memory is required and providing details about where space was made.

Parameters:

Name	Type	Description	Default
`bom`	`BOM`		required
`permission_map`	`Optional[Mapping[ofrak_type.memory_permissions.MemoryPermissions, Iterable[ofrak_type.memory_permissions.MemoryPermissions]]]`	a map that assigns patch segment-local permissions to possible destination permissions. available memory pool is evaluated in order! Ex: a developer wants to enable allocation of RO strings from .rodata in an RX .text section.	`None`

Returns:

Type	Description
`PatchRegionConfig`	information required to generate the linker directive script

Source code in ofrak/core/free_space.py

async def allocate_bom(
    self,
    bom: BOM,
    permission_map: Optional[Mapping[MemoryPermissions, Iterable[MemoryPermissions]]] = None,
) -> PatchRegionConfig:
    """
    Responsible for allocating the patches if free memory is required and
    providing details about where space was made.

    :param bom:
    :param permission_map: a map that assigns patch segment-local permissions to possible
    destination permissions. available memory pool is evaluated in order!
    Ex: a developer wants to enable allocation of RO strings from .rodata in an RX .text section.

    :return: information required to generate the linker directive script
    """
    segments_to_allocate: List[Tuple[AssembledObject, Segment]] = []
    for obj in bom.object_map.values():
        for segment in obj.segment_map.values():
            segments_to_allocate.append((obj, segment))

    # Allocate largest segments first
    segments_to_allocate.sort(key=lambda o_s: o_s[1].length, reverse=True)
    segments_by_object: Dict[str, List[Segment]] = defaultdict(list)
    for obj, segment in segments_to_allocate:
        vaddr, final_size = 0, 0
        if segment.length == 0:
            continue
        if permission_map is not None:
            possible_perms = permission_map[segment.access_perms]
        else:
            possible_perms = (segment.access_perms,)
        for candidate_permissions in possible_perms:
            try:
                allocs = await self.allocate(
                    candidate_permissions,
                    segment.length,
                    min_fragment_size=segment.length,
                    alignment=bom.segment_alignment,
                )
                allocation = next(iter(allocs))
                vaddr = allocation.start
                final_size = allocation.length()
                break
            except FreeSpaceAllocationError:
                continue
        if vaddr == 0 or final_size == 0:
            raise FreeSpaceAllocationError(
                f"Could not find enough free space for access perms {possible_perms} and "
                f"length {segment.length}"
            )
        segments_by_object[obj.path].append(
            Segment(
                segment_name=segment.segment_name,
                vm_address=vaddr,
                offset=segment.offset,
                is_entry=segment.is_entry,
                length=final_size,
                access_perms=segment.access_perms,
            )
        )

    all_segments: Dict[str, Tuple[Segment, ...]] = {
        object_path: tuple(segments) for object_path, segments in segments_by_object.items()
    }

    return PatchRegionConfig(bom.name + "_patch", immutabledict(all_segments))

`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=None)` `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`	`ComponentConfig`	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.	`None`

Returns:

Type	Description
`Allocatable`	The analysis results

Source code in ofrak/core/free_space.py

async def analyze(self, resource: Resource, config: ComponentConfig = 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.

The modifier allows for an optional "stub", bytes to be injected at the beginning of the target resource. The stub bytes are not marked as 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_patch(freed_range, config.stub, config.fill)
    parent = await resource.get_parent()
    patch_offset = (await resource.get_data_range_within_parent()).start
    patch_range = freed_range.translate(patch_offset - freed_range.start)

    # Grab tags, so they can be saved to the stub.
    # At some point, it might be nice to save the attributes as well.
    current_tags = resource.get_tags()
    # One interesting side effect here is the Resource used to call this modifier no longer exists
    # when this modifier returns. This can be confusing. Would an update work better in this case?
    await resource.delete()
    await resource.save()

    # Patch in the patch_data
    await parent.run(BinaryPatchModifier, BinaryPatchConfig(patch_offset, patch_data))

    free_offset = len(config.stub)

    if len(config.stub) > 0:
        # Create the stub
        await parent.create_child_from_view(
            MemoryRegion(mem_region_view.virtual_address, len(config.stub)),
            data_range=Range.from_size(patch_range.start, len(config.stub)),
            additional_tags=current_tags,
        )

    # Create the FreeSpace child
    await parent.create_child_from_view(
        FreeSpace(
            mem_region_view.virtual_address + free_offset,
            mem_region_view.size - free_offset,
            config.permissions,
        ),
        data_range=Range(patch_range.start + free_offset, patch_range.end),
    )

`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.
`stub`	`bytes`	Bytes for a stub to be injected before the free space. The stub will not be marked as FreeSpace.
`fill`	`bytes`	Pattern of 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 fill bytes (b'' by default).

The modifier supports optionally injecting a "stub", bytes at the beginning of the targeted range that will not be marked as 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`	`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):
    freed_range = config.range_to_remove
    mem_region_view = await resource.view_as(MemoryRegion)
    if not freed_range.within(mem_region_view.vaddr_range()):
        raise ModifierError(
            f"Free space range, {freed_range}, must lie within target memory"
            f"region range, {mem_region_view.vaddr_range()}"
        )

    await _find_and_delete_overlapping_children(resource, freed_range)

    patch_offset = mem_region_view.get_offset_in_self(freed_range.start)
    patch_range = Range.from_size(patch_offset, freed_range.length())
    patch_data = _get_patch(freed_range, config.stub, config.fill)
    await mem_region_view.resource.run(
        BinaryPatchModifier, BinaryPatchConfig(patch_offset, patch_data)
    )

    free_offset = len(config.stub)
    await mem_region_view.resource.create_child_from_view(
        FreeSpace(
            freed_range.start + free_offset,
            freed_range.length() - free_offset,
            config.permissions,
        ),
        data_range=Range(patch_range.start + free_offset, patch_range.end),
    )

`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).
`stub`	`bytes`	Bytes for a stub to be injected before the free space. If a stub is specified, then the FreeSpace created will decrease in size. For example, with a stub of b"HA" and range_to_remove=Range(4,10), the final FreeSpace will end up corresponding to Range(6,10).
`fill`	`bytes`	Pattern of 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)

free_space.py

ofrak.core.free_space

Allocatable (ResourceView) dataclass

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

allocate_bom(self, bom, permission_map=None) async

FreeSpace (MemoryRegion) dataclass

FreeSpaceAllocation (ComponentConfig) dataclass

FreeSpaceAnalyzer (Analyzer)

analyze(self, resource, config=None) async

FreeSpaceModifier (Modifier)

modify(self, resource, config) async

FreeSpaceModifierConfig (ComponentConfig) dataclass

PartialFreeSpaceModifier (Modifier)

modify(self, resource, config) async

PartialFreeSpaceModifierConfig (ComponentConfig) dataclass

RemoveFreeSpaceModifier (Modifier)

modify(self, resource, config) async

`ofrak.core.free_space`

`Allocatable (ResourceView)` `dataclass`

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

`allocate_bom(self, bom, permission_map=None)` `async`

`FreeSpace (MemoryRegion)` `dataclass`

`FreeSpaceAllocation (ComponentConfig)` `dataclass`

`FreeSpaceAnalyzer (Analyzer)`

`analyze(self, resource, config=None)` `async`

`FreeSpaceModifier (Modifier)`

`modify(self, resource, config)` `async`

`FreeSpaceModifierConfig (ComponentConfig)` `dataclass`

`PartialFreeSpaceModifier (Modifier)`

`modify(self, resource, config)` `async`

`PartialFreeSpaceModifierConfig (ComponentConfig)` `dataclass`

`RemoveFreeSpaceModifier (Modifier)`

`modify(self, resource, config)` `async`