I'm fairly sure Acorn had an approach to relocating code at one point: I think the ROM image was followed by a list of patch-up addresses. I'm not sure though that there's any approach in Acorn land to run code where the load address is not known until load time - it would be useful if there were, because in Acorn land the free RAM, after OS use, can start (and end) at a variety of places. Sometimes an application might load at 400, or at E00, or 1900, or 8000, or B800, depending. Other places too.

What would be nice then, would be an approach and a format which will run anywhere, possibly relocating itself. At least two things are needed:
- an executable header which is position independent and able to discover its location
- a means of patching up absolute addresses in the code
and possibly
- a means of block-moving the loaded and patched code to a different location

For discovering location, I had this thought:
- Use a few bytes just below 0200, having first saved those values on the stack
- place a routine there, call it, and it will examine the stack and report back

For example, this code
would pick its own return address (-1) from the stack. Being 8 bytes, we'd place it at 01f8, and we'd need first to save those 8 bytes from the bottom of the stack, on the stack. Something like

(Edit: we need first to be sure the stack is already at least 8 bytes deep! Maybe check S, or just subtract from S, or do a bunch of pushes.)

Then we'd need to store the code using immediate values

Now we can call the code, and then repair the stack.

(We will of course need some workspace: in Acorn land there are known areas of zero page available to applications. Possibly it's worth somehow parameterising which section of zero page we use. We can use the stack to save anything we might intend to trample on temporarily.)

How to patch up absolute addresses? One approach is to have a list of addresses to patch, or possibly delta-encode that list. Or possibly use a byte-stuffing tactic and have a special value to stand for each address MSB.

(If I've made any small mistakes, please let me know by PM and I'll correct them.)

But more interesting: have I missed some good way to tackle this, or not noticed some obstacle? Or prior art?

Interesting topic.

If you can exclude the possibility of NMI, then I think you can determine the load address of the code in a more efficient way that doesn't involve copying code to the stack.

You should end up with the adress of .start in $80, $81

I've not tested this so the could be bugs, but you get the idea....

Dave

Ah yes, that's quite nice.

BTW I realised we can stash 8 bytes from the bottom of the stack even if the stack has fewer bytes on it, if we're careful about ordering. Instead of

something like

The approach that Dave showed was what I was expecting to see.

Do the later CMOS 6502 versions offer any advantages in getting the return address off the stack?

Mark

Well, at minimum you have access to PLX/Y and PHX/Y instead of having to transfer through A: But an NMOS compatible method is to use the stack pointer directly as an index: On the '816 you can directly do stack-relative addressing: But then again, on the '816 you also have PER, which directly allows you to determine your current execution address or any 16-bit offset from it - so you can directly obtain a pointer to the reloc table, and another to your load base. You can then do stack-indirect addressing to rewrite the relevant places, without having to move the pointer to Direct Page first. This on top of the fact that you're less reliant on absolute addresses in the first place.

The stack isn't the first place I would choose to store executable code. A bit of carnal knowledge of the system should be able to scare up eight contiguous bytes elsewhere, I would imagine. Michael J. Mahon (among others in Apple ][ land) just JSR to a known RTS in ROM then quickly examine the ghost of the return address, presumably before it gets overwritten by an IRQ or NMI.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

If we *were* to use the stack to store temporary executable code, this might be a safer way - no interrupt avoidance necessary: This does still require three bytes in ZP to get a jump to the correct stack offset, because the 'C02 doesn't have JSR (abs,X).

Just found this from my records:

EDASM: Relocatable Code with RBOOT & RLOAD.

Honestly, this seems like a great thing to integrate into your OS kernel, if it plans to allow loading user programs at arbitrary addresses. Since the OS itself knows where it loaded the code, much of these shenanigans can be avoided. Or it can be a subroutine called by the subject program at a documented entry point, also allowing relocation to be redone when overlays are loaded.

Bonus functionality: dynamic library linking.

Yes, it would be a good feature of a loader. But failing that, it's a preamble. Fitting in one page for bonus points! (I would personally also assume that the load address and eventual start address were page-aligned.)

Is the goal specifically to fix absolute addresses at load time, or just to make it so code is not stuck at the addresses determined at assembly time? Doing the latter and making it movable, even after it has been loaded is, as we all know, an inefficient proposition on the '02; but it can be done. Chapter 12 of my 6502 stacks treatise, on "Where-am-I?" routines, addresses this. About 3/4 of the way down the page, starting where it says, "However, there's something you can do to gain a small improvement in performance", it shows ways to cut some of the overhead by requiring movement to be in increments of 256 bytes so at least the low byte can be fixed at assembly time rather than having to be calculated at run time. The minimal price you pay to get this added performance is some memory waste with gaps between programs, averaging about 128 bytes. Having for example five relocatable programs in memory at once then (with four gaps) would, on the average, result in somewhere around two pages wasted, or less than 1% of the 6502's memory map space (although a somewhat higher percentage of available RAM).

The following chapter is about the 65816's instructions and capabilities relevant to stacks and relocatable code, and 65c02 code which partially synthesizes some of them. Again, it's inefficient on the '02, but it can be done.

On my workbench computer with onboard Forth, any code I load gets compiled (if Forth) or assembled (if assembly language) on the fly, from source code every time; so although there's nothing specifically geared toward making code relocatable, it turns out to be anyway. (I just can't move it after it's loaded.)

For an impressive 6502 OS that allows program relocation at the time of loading (but not after), see André Fachat's GeckOS scalable preëmptive multitasking/multithreading OS which has Unix-like features, dynamic memory management, relocatable file format, a standard library, internet support, virtual consoles, and remote login, and runs on a Commodore 64 and other 6502 platforms. Undefined address references are solved at load time. http://6502.org/users/andre/osa/index.html I have not taken the time to learn and understand it myself.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Ah, yes, thanks for the pointer to GeckOS.

I am imagining an assembly-time process which detects the bytes which will need to be changed at load time, instruments the executable and prepends the loader. (One idea I've seen is to assemble twice, to different target addresses, and compare the results, as a way to find the bytes which will need to be changed at load time.)

In Acorn land, Basic programs are always loaded at PAGE, the lower boundary of usable RAM, wherever that might be. So a loader which is, at least initially and functionally, a Basic program, would naturally land in a reasonably convenient location. This might be similar to the Apple II case.

Whether or not it's integrated into the OS, it strikes me that a loader that runs independently of the subject program may have an easier time of performing the relocation. If you have a filesystem - especially one that supports random access, but this is not strictly necessary - then you could structure program binaries so that they are not blindly loaded as a block into some area of RAM, but instead consist of a header containing a relocation table, followed by the code and data. A separate loader program would process this file with full advance knowledge of the load address.

Yet another approach, which lends itself well to modular programming techniques, is to "pre-link" the binaries so that they can be loaded (in any reasonable combination) at pre-chosen addresses, without needing relocation or symbol resolution at runtime. This may require generating extra copies of each binary with the modifications already performed, alongside the original which retains the data necessary to do it again.

Were you thinking of something like an ELF format file and ELF loader? ELF is a generic format that supports relocatable files.

_________________
http://www.finitron.ca

I wasn't thinking of a structured file, although that would be a solution, but it would need a loader. If writing an OS, one would write a loader, and hopefully give it useful capabilities! (The Amiga loader also springs to mind: it can relocate as it loads, which is needed in the Amiga world of multitasking without an MMU.)

But, I was thinking of an executable which can be loaded and run by a dimwitted loader, but which contains a set of things: an executable relocater, the binary, the information needed to patch the binary.

It might be that the best form for the initial or outermost section is a Basic stub: in Acorn, and probably Apple, and maybe Commodore, worlds, Basic will load a program into the lowest free space, wherever that might be. The Basic stub can call the payload which is appended to it, which is the set of things listed above. Or one could write the relocater in Basic, but that would probably be larger and certainly slower.

There's certainly room for two discussions on this: the prepended "loader" which is loaded by a dimwitted OS, which was my original train of thought; and the design of a full-featured loader which an OS might usefully contain.