ref: 599ce757a1f644aba35d692cec68202944f7163f
dir: /src/link/assign.c/
/* * This file is part of RGBDS. * * Copyright (c) 2019, Eldred Habert and RGBDS contributors. * * SPDX-License-Identifier: MIT */ #include <inttypes.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include "link/assign.h" #include "link/section.h" #include "link/symbol.h" #include "link/object.h" #include "link/main.h" #include "link/output.h" #include "error.h" #include "helpers.h" #include "linkdefs.h" struct MemoryLocation { uint16_t address; uint32_t bank; }; struct FreeSpace { uint16_t address; uint16_t size; struct FreeSpace *next, *prev; }; // Table of free space for each bank struct FreeSpace *memory[SECTTYPE_INVALID]; uint64_t nbSectionsToAssign; // Init the free space-modelling structs static void initFreeSpace(void) { for (enum SectionType type = 0; type < SECTTYPE_INVALID; type++) { memory[type] = malloc(sizeof(*memory[type]) * nbbanks(type)); if (!memory[type]) err("Failed to init free space for region %d", type); for (uint32_t bank = 0; bank < nbbanks(type); bank++) { memory[type][bank].next = malloc(sizeof(*memory[type][0].next)); if (!memory[type][bank].next) err("Failed to init free space for region %d bank %" PRIu32, type, bank); memory[type][bank].next->address = sectionTypeInfo[type].startAddr; memory[type][bank].next->size = sectionTypeInfo[type].size; memory[type][bank].next->next = NULL; memory[type][bank].next->prev = &memory[type][bank]; } } } /* * Assigns a section to a given memory location * @param section The section to assign * @param location The location to assign the section to */ static void assignSection(struct Section *section, struct MemoryLocation const *location) { section->org = location->address; section->bank = location->bank; // Propagate the assigned location to all UNIONs/FRAGMENTs // so `jr` patches in them will have the correct offset for (struct Section *next = section->nextu; next != NULL; next = next->nextu) { next->org = section->org; next->bank = section->bank; } nbSectionsToAssign--; out_AddSection(section); } /* * Checks whether a given location is suitable for placing a given section * This checks not only that the location has enough room for the section, but * also that the constraints (alignment...) are respected. * @param section The section to be placed * @param freeSpace The candidate free space to place the section into * @param location The location to attempt placing the section at * @return True if the location is suitable, false otherwise. */ static bool isLocationSuitable(struct Section const *section, struct FreeSpace const *freeSpace, struct MemoryLocation const *location) { if (section->isAddressFixed && section->org != location->address) return false; if (section->isAlignFixed && ((location->address - section->alignOfs) & section->alignMask)) return false; if (location->address < freeSpace->address) return false; return location->address + section->size <= freeSpace->address + freeSpace->size; } /* * Finds a suitable location to place a section at. * @param section The section to be placed * @param location A pointer to a location struct that will be filled * @return A pointer to the free space encompassing the location, or NULL if * none was found */ static struct FreeSpace *getPlacement(struct Section const *section, struct MemoryLocation *location) { static uint16_t curScrambleROM = 1; static uint8_t curScrambleWRAM = 1; static uint8_t curScrambleSRAM = 1; // Determine which bank we should start searching in if (section->isBankFixed) { location->bank = section->bank; } else if (scrambleROMX && section->type == SECTTYPE_ROMX) { location->bank = curScrambleROM++; if (curScrambleROM > scrambleROMX) curScrambleROM = 1; } else if (scrambleWRAMX && section->type == SECTTYPE_WRAMX) { location->bank = curScrambleWRAM++; if (curScrambleWRAM > scrambleWRAMX) curScrambleWRAM = 1; } else if (scrambleSRAM && section->type == SECTTYPE_SRAM) { location->bank = curScrambleSRAM++; if (curScrambleSRAM > scrambleSRAM) curScrambleSRAM = 0; } else { location->bank = sectionTypeInfo[section->type].firstBank; } struct FreeSpace *space; for (;;) { // Switch to the beginning of the next bank #define BANK_INDEX (location->bank - sectionTypeInfo[section->type].firstBank) space = memory[section->type][BANK_INDEX].next; if (space) location->address = space->address; // Process locations in that bank while (space) { // If that location is OK, return it if (isLocationSuitable(section, space, location)) return space; // Go to the next *possible* location if (section->isAddressFixed) { // If the address is fixed, there can be only // one candidate block per bank; if we already // reached it, give up. if (location->address < section->org) location->address = section->org; else // Try again in next bank space = NULL; } else if (section->isAlignFixed) { // Move to next aligned location // Move back to alignment boundary location->address -= section->alignOfs; // Ensure we're there (e.g. on first check) location->address &= ~section->alignMask; // Go to next align boundary and add offset location->address += section->alignMask + 1 + section->alignOfs; } else { // Any location is fine, so, next free block space = space->next; if (space) location->address = space->address; } // If that location is past the current block's end, // go forwards until that is no longer the case. while (space && location->address >= space->address + space->size) space = space->next; // Try again with the new location/free space combo } if (section->isBankFixed) return NULL; // Try again in the next bank location->bank++; if (location->bank > sectionTypeInfo[section->type].lastBank) return NULL; #undef BANK_INDEX } } /* * Places a section in a suitable location, or error out if it fails to. * @warning Due to the implemented algorithm, this should be called with * sections of decreasing size. * @param section The section to place */ static void placeSection(struct Section *section) { struct MemoryLocation location; // Specially handle 0-byte SECTIONs, as they can't overlap anything if (section->size == 0) { // Unless the SECTION's address was fixed, the starting address // is fine for any alignment, as checked in sect_DoSanityChecks. location.address = section->isAddressFixed ? section->org : sectionTypeInfo[section->type].startAddr; location.bank = section->isBankFixed ? section->bank : sectionTypeInfo[section->type].firstBank; assignSection(section, &location); return; } // Place section using first-fit decreasing algorithm // https://en.wikipedia.org/wiki/Bin_packing_problem#First-fit_algorithm struct FreeSpace *freeSpace = getPlacement(section, &location); if (freeSpace) { assignSection(section, &location); // Split the free space bool noLeftSpace = freeSpace->address == section->org; bool noRightSpace = freeSpace->address + freeSpace->size == section->org + section->size; if (noLeftSpace && noRightSpace) { // The free space is entirely deleted freeSpace->prev->next = freeSpace->next; if (freeSpace->next) freeSpace->next->prev = freeSpace->prev; // If the space is the last one on the list, set its // size to 0 so it doesn't get picked, but don't free() // it as it will be freed when cleaning up free(freeSpace); } else if (!noLeftSpace && !noRightSpace) { // The free space is split in two struct FreeSpace *newSpace = malloc(sizeof(*newSpace)); if (!newSpace) err("Failed to split new free space"); // Append the new space after the chosen one newSpace->prev = freeSpace; newSpace->next = freeSpace->next; if (freeSpace->next) freeSpace->next->prev = newSpace; freeSpace->next = newSpace; // Set its parameters newSpace->address = section->org + section->size; newSpace->size = freeSpace->address + freeSpace->size - newSpace->address; // Set the original space's new parameters freeSpace->size = section->org - freeSpace->address; // address is unmodified } else { // The amount of free spaces doesn't change: resize! freeSpace->size -= section->size; if (noLeftSpace) // The free space is moved *and* resized freeSpace->address += section->size; } return; } // Please adjust depending on longest message below char where[64]; if (section->isBankFixed && nbbanks(section->type) != 1) { if (section->isAddressFixed) snprintf(where, 64, "at $%02" PRIx32 ":%04" PRIx16, section->bank, section->org); else if (section->isAlignFixed) snprintf(where, 64, "in bank $%02" PRIx32 " with align mask %" PRIx16, section->bank, (uint16_t)~section->alignMask); else snprintf(where, 64, "in bank $%02" PRIx32, section->bank); } else { if (section->isAddressFixed) snprintf(where, 64, "at address $%04" PRIx16, section->org); else if (section->isAlignFixed) snprintf(where, 64, "with align mask %" PRIx16 " and offset %" PRIx16, (uint16_t)~section->alignMask, section->alignOfs); else strcpy(where, "anywhere"); } // If a section failed to go to several places, nothing we can report if (!section->isBankFixed || !section->isAddressFixed) errx("Unable to place \"%s\" (%s section) %s", section->name, sectionTypeInfo[section->type].name, where); // If the section just can't fit the bank, report that else if (section->org + section->size > endaddr(section->type) + 1) errx("Unable to place \"%s\" (%s section) %s: section runs past end of region ($%04x > $%04x)", section->name, sectionTypeInfo[section->type].name, where, section->org + section->size, endaddr(section->type) + 1); // Otherwise there is overlap with another section else errx("Unable to place \"%s\" (%s section) %s: section overlaps with \"%s\"", section->name, sectionTypeInfo[section->type].name, where, out_OverlappingSection(section)->name); } struct UnassignedSection { struct Section *section; struct UnassignedSection *next; }; #define BANK_CONSTRAINED (1 << 2) #define ORG_CONSTRAINED (1 << 1) #define ALIGN_CONSTRAINED (1 << 0) static struct UnassignedSection *unassignedSections[1 << 3] = {0}; static struct UnassignedSection *sections; /* * Categorize a section depending on how constrained it is * This is so the most-constrained sections are placed first * @param section The section to categorize * @param arg Callback arg, unused */ static void categorizeSection(struct Section *section, void *arg) { (void)arg; uint8_t constraints = 0; if (section->isBankFixed) constraints |= BANK_CONSTRAINED; if (section->isAddressFixed) constraints |= ORG_CONSTRAINED; // Can't have both! else if (section->isAlignFixed) constraints |= ALIGN_CONSTRAINED; struct UnassignedSection **ptr = &unassignedSections[constraints]; // Insert section while keeping the list sorted by decreasing size while (*ptr && (*ptr)->section->size > section->size) ptr = &(*ptr)->next; sections[nbSectionsToAssign].section = section; sections[nbSectionsToAssign].next = *ptr; *ptr = §ions[nbSectionsToAssign]; nbSectionsToAssign++; } void assign_AssignSections(void) { verbosePrint("Beginning assignment...\n"); // Initialize assignment // Generate linked lists of sections to assign sections = malloc(sizeof(*sections) * nbSectionsToAssign + 1); if (!sections) err("Failed to allocate memory for section assignment"); initFreeSpace(); nbSectionsToAssign = 0; sect_ForEach(categorizeSection, NULL); // Place sections, starting with the most constrained // Specially process fully-constrained sections because of overlaying struct UnassignedSection *sectionPtr = unassignedSections[BANK_CONSTRAINED | ORG_CONSTRAINED]; verbosePrint("Assigning bank+org-constrained...\n"); while (sectionPtr) { placeSection(sectionPtr->section); sectionPtr = sectionPtr->next; } // If all sections were fully constrained, we have nothing left to do if (!nbSectionsToAssign) return; // Overlaying requires only fully-constrained sections verbosePrint("Assigning other sections...\n"); if (overlayFileName) { fprintf(stderr, "FATAL: All sections must be fixed when using an overlay file"); uint8_t nbSections = 0; for (int8_t constraints = BANK_CONSTRAINED | ALIGN_CONSTRAINED; constraints >= 0; constraints--) { for (sectionPtr = unassignedSections[constraints]; sectionPtr; sectionPtr = sectionPtr->next) { fprintf(stderr, "%c \"%s\"", nbSections == 0 ? ';': ',', sectionPtr->section->name); nbSections++; if (nbSections == 10) goto max_out; } } max_out: if (nbSectionsToAssign != nbSections) fprintf(stderr, " and %" PRIu64 " more", nbSectionsToAssign - nbSections); fprintf(stderr, " %sn't\n", nbSectionsToAssign == 1 ? "is" : "are"); exit(1); } // Assign all remaining sections by decreasing constraint order for (int8_t constraints = BANK_CONSTRAINED | ALIGN_CONSTRAINED; constraints >= 0; constraints--) { sectionPtr = unassignedSections[constraints]; while (sectionPtr) { placeSection(sectionPtr->section); sectionPtr = sectionPtr->next; } if (!nbSectionsToAssign) return; } unreachable_(); } void assign_Cleanup(void) { for (enum SectionType type = 0; type < SECTTYPE_INVALID; type++) { for (uint32_t bank = 0; bank < nbbanks(type); bank++) { struct FreeSpace *ptr = memory[type][bank].next; while (ptr) { struct FreeSpace *next = ptr->next; free(ptr); ptr = next; } } free(memory[type]); } free(sections); }