6502.org • View topic - A way to relocate code

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

A way to relocate code

Page 1 of 2

[ 25 posts ]

Go to page 1, 2 Next

Previous topic | Next topic

Author

Message

BillG

Post subject: A way to relocate code

Posted: Thu Sep 03, 2020 12:24 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

Many instruction sets do not facilitate the writing of position independent code.

8080 machine code is not inherently relocatable, but the MOVCPM command allows the location of the operating system to be changed.

How do they do this?

Embedded in MOVCPM is a bit map of the bytes in the system image indicating which need to be adjusted. Their method only allows movement in increments of 256 bytes.

How do they create this table?

One way is to build the system twice, ORGed a multiple of 256 bytes apart. The bytes which differ are the ones dependent upon the load location.

I want to build a similar system but one allowing an arbitrary relocation offset. If an image is built at one byte and 256 byte offsets, two bit maps can be built to specify which bytes need to be adjusted with the low and high bytes of the load offset.

Those bytes which differ in the off-by-one image but not in the off-by-256 one are to be adjusted with the low byte of the relocation offset.

Comments?

Code:

 0200                     00001          org    $200
                          00002
 0200                     00003 Start
 0200 4C 02FF         [3] 00004          jmp    Target
                          00005
 0203 FF                  00006          fcb    <Target
 0204 02FF                00007          fdb    Target
 0206 02                  00008          fcb    >Target
                          00009
 0207                     00010          rmb    255-3-2-1-1
                          00011
 02FF                     00012 Target

Code:

 0201                     00001          org    $201
                          00002
 0201                     00003 Start
 0201 4C 0300         [3] 00004          jmp    Target
                          00005
 0204 00                  00006          fcb    <Target
 0205 0300                00007          fdb    Target
 0207 03                  00008          fcb    >Target
                          00009
 0208                     00010          rmb    255-3-2-1-1
                          00011
 0300                     00012 Target

Code:

 0300                     00001          org    $300
                          00002
 0300                     00003 Start
 0300 4C 03FF         [3] 00004          jmp    Target
                          00005
 0303 FF                  00006          fcb    <Target
 0304 03FF                00007          fdb    Target
 0306 03                  00008          fcb    >Target
                          00009
 0307                     00010          rmb    255-3-2-1-1
                          00011
 03FF                     00012 Target

Top

White Flame

Post subject: Re: A way to relocate code

Posted: Thu Sep 03, 2020 1:12 pm

Joined: Tue Jul 24, 2012 2:27 am
Posts: 679

The .o65 output from ca65/ld65 generates relocation tables. These come from the linker itself, which resolves the references into the output bytes, knowing which references refer to locations within the binary itself, vs which are outside of it.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

Top

vbc

Post subject: Re: A way to relocate code

Posted: Thu Sep 03, 2020 3:16 pm

Joined: Thu Apr 23, 2020 5:04 pm
Posts: 53

BillG wrote:

I used a similar approach to create a relocatable linker library for the SANE fp routines. There is an AppleII tool that creates binaries using specified addresses. The code uses two separate zero page areas which makes it a bit more complicated, but that can be handled by suitable choice of target addresses (in your case using an offset of e.g. 0x1122 should enable you to extract the information from a single offset image).

It works well, but if you create the images from assembly, be careful that the assembler does not do any optimizations in one image that it cannot do in the other. Personally, if the source was available, I would have the assembler and linker create the relocation information.

Top

GARTHWILSON

Post subject: Re: A way to relocate code

Posted: Thu Sep 03, 2020 6:43 pm

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8543
Location: Southern California

BillG wrote:

Many instruction sets do not facilitate the writing of position-independent code.

[...] method only allows movement in increments of 256 bytes.

[...] I want to build a similar system but one allowing an arbitrary relocation offset.

[...] specify which bytes need to be adjusted with the low and high bytes of the load offset.

How about making it so the code can be relocated even after it's loaded, like to be able to delete a program you're done with, and move others so the free memory space is all at one end, available to load a bigger program? IOW, memory will not be fragmented. (If a program is already active, you probably would only move it when it's at a good pausing point so it doesn't have actual addresses on the stack that would suddenly become invalid as a result of the move.)

From the 6502 stacks treatise's relocatable-code page at http://wilsonminesco.com/stacks/where-am-I.html :

Let's admit right up front: The 6502 is poorly suited for relocatable code. It's not totally incapable of it though, nor does every application need to wring maximum performance out of the processor. We sometimes accept compromises in performance to get another desired benefit.
and then it continues with ideas for how to do it. A linker is not involved. You can however reduce the overhead if you only allow movement in increments of 256 bytes. The overall memory penalty is less than you might think.

_________________
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?

Top

BillG

Post subject: Re: A way to relocate code

Posted: Thu Sep 03, 2020 8:00 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

White Flame wrote:

Thanks, but that looks very complicated.

Allow me to clarify more specifically what I am after.

The FLEX EXEC command on the 6809 loads into the Utility Command Space. It checks MEMEND and copies itself to the top of the main RAM and lowers MEMEND to protect itself. EXEC is a utility to execute a series of commands from a file. MEMEND is a FLEX system variable which contains the address of the highest usable location of user RAM.

It does its business, then restores MEMEND before exiting.

I am looking to build something similar for the 6502 and 6800 neither of which readily supports writing position independent code. EXEC for the 6800 currently loads at a fixed location just below the 32K mark, meaning it cannot be used on a machine with less than 32K of main RAM or if other "terminate and stay resident" programs are already loaded into that area.

I prefer something fairly simple which will work with code generated by most tools, though I am currently using either the FLEX ASMB assembler or my own cross assembler. I do not want to be tied to one assembler, compiler or linker. Eventually, it would be nice to be able to build a relocatable program entirely using tools hosted by FLEX. The bit map builder tool originally runs on a PC, but will later be built as a FLEX program.

If this works out well, I may try to create something like MOVCPM to allow the end user to move a 6502 FLEX system image without having to rebuild it from source.

Top

BillG

Post subject: Re: A way to relocate code

Posted: Thu Sep 03, 2020 8:01 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

vbc wrote:

(in your case using an offset of e.g. 0x1122 should enable you to extract the information from a single offset image).

Interesting. I'll look into that.

Top

White Flame

Post subject: Re: A way to relocate code

Posted: Fri Sep 04, 2020 2:38 am

Joined: Tue Jul 24, 2012 2:27 am
Posts: 679

BillG wrote:

Thanks, but that looks very complicated.

Well, relocation is a complicated problem. What if, because of the way you pack pointers, you have something like this?

Code:

lda #(>some_pointer >> 1)

Code:

lda #((foo & $f0) | (bar & $0f))

Relocating addresses does not always result in constant deltas to the assembled bytes created from the address. Plus, if you have page alignment requirements in your code or data, you cannot freely relocate on a sub-page granularity and the relocater should enforce that accordingly. Sometimes you have multiple independent zones of relocation, like allocating zeropage, allocating main code, allocating a buffer for dynamic use, and resolving references to dynamic imports.

If you create a simpler relocater without some of these considerations, then you can't safely relocate arbitrary code. All the constraints of the relocater must be enumerated as part of your mandated coding style for use in your system. (Note that .o65 might not be able to relocate those above examples either, I'm not sure. But to my knowledge it's the most mature and well known attempt at general relocating.)

Certainly if you're creating code for a memory-sharing system, tactics to reduce the footprint will be used, and those tricks will be confounding factors in relocating.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

Top

barrym95838

Post subject: Re: A way to relocate code

Posted: Fri Sep 04, 2020 5:11 am

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1949
Location: Sacramento, CA, USA

White Flame wrote:

... if you have page alignment requirements in your code or data, you cannot freely relocate on a sub-page granularity ...

Woz did this early and often. I'm sure he had company.

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

Top

BillG

Post subject: Re: A way to relocate code

Posted: Fri Sep 04, 2020 12:19 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

GARTHWILSON wrote:

You can however reduce the overhead if you only allow movement in increments of 256 bytes. The overall memory penalty is less than you might think.

You are right, but not for that reason.

It turns out that my original analysis was flawed.

Consider this:

Code:

fcb >Address

The information is not available at load time whether an adjustment to the missing low byte of the address will carry into the high byte.

So I will restrict relocation to multiples of 256.

For reference, this is the "resident" portion of the EXEC command; it reads and executes commands from a text file.

Code:

.0B03                     00220 DoExec
.0B03 A2 C2           [2] 00221          ldx    #<ExecFCB  ; Get name of file to execute
.0B05 A9 0B           [2] 00222          lda    #>ExecFCB
.0B07 20 022D         [6] 00223          jsr    GETFIL    ; Get File Specification
.0B0A B0 4B (0B57)  [2/3] 00224          bcs    Error     ; Branch if error
.                         00225
.0B0C A0 01           [2] 00226          ldy    #ExtTXT   ; Default to .TXT
.0B0E A2 C2           [2] 00227          ldx    #<ExecFCB
.0B10 A9 0B           [2] 00228          lda    #>ExecFCB
.0B12 20 0233         [6] 00229          jsr    SETEXT    ; Set Extension
.                         00230
.0B15 A9 01           [2] 00231          lda    #FMSO4R   ; Open file for reading
.0B17 8D 0BC2         [4] 00232          sta    ExecFCB+FCBFun
.0B1A A2 C2           [2] 00233          ldx    #<ExecFCB
.0B1C A9 0B           [2] 00234          lda    #>ExecFCB
.0B1E 20 0260         [6] 00235          jsr    FMS
.0B21 D0 34 (0B57)  [2/3] 00236          bne    Error     ; If error
.                         00237
.0B23 A9 04           [2] 00238          lda    #FMSCLO   ; Close the file
.0B25 8D 0BC2         [4] 00239          sta    ExecFCB+FCBFun
.0B28 A2 C2           [2] 00240          ldx    #<ExecFCB
.0B2A A9 0B           [2] 00241          lda    #>ExecFCB
.0B2C 20 0260         [6] 00242          jsr    FMS
.0B2F D0 26 (0B57)  [2/3] 00243          bne    Error     ; If error
.                         00244
.0B31 A9 01           [2] 00245          lda    #1        ; Set FCB to read from the file
.0B33 8D 0BC4         [4] 00246          sta    ExecFCB+FCBSts
.0B36 A9 00           [2] 00247          lda    #0
.0B38 8D 0BC2         [4] 00248          sta    ExecFCB+FCBFun
.                         00249
.0B3B                     00250 ExecLoop
.0B3B 20 0B5D         [6] 00251          jsr    Readln    ; Read a command
.0B3E B0 17 (0B57)  [2/3] 00252          bcs    Error     ; If error
.                         00253
.0B40 AD 0BC0         [4] 00254          lda    EOF       ; End of file?
.0B43 D0 0C (0B51)  [2/3] 00255          bne    Exit      ; Yes
.                         00256
.0B45 20 024B         [6] 00257          jsr    DOCMND    ; Execute the command
.0B48 F0 F1 (0B3B)  [2/3] 00258          beq    ExecLoop  ; If no error
.                         00259
.0B4A A2 A1           [2] 00260          ldx    #<Aborted  ; Say 'EXEC ABORTED'
.0B4C A9 0B           [2] 00261          lda    #>Aborted
.0B4E 20 021E         [6] 00262          jsr    PSTRNG
.                         00263
.0B51                     00264 Exit
.0B51 20 025D         [6] 00265          jsr    FMSCLS    ; Close FMS
.                         00266
.0B54 4C 0203         [3] 00267          jmp    WARMS     ; Back to FLEX
.                         00268
.0B57                     00269 Error
.0B57 20 023F         [6] 00270          jsr    RPTERR    ; Report Error
.                         00271
.0B5A 4C 0B51         [3] 00272          jmp    Exit
.                         00273
.                         00274 ;
.                         00275 ; Read a line
.                         00276 ;
.0B5D                     00277 Readln
.0B5D A2 00           [2] 00278          ldx    #<CmdBuf  ; Point to input buffer
.0B5F 8E 02A4         [4] 00279          stx    LINBUF
.0B62 A2 01           [2] 00280          ldx    #>CmdBuf
.0B64 8E 02A5         [4] 00281          stx    LINBUF+1
.                         00282
.0B67 A2 00           [2] 00283          ldx    #0        ; Index first character of buffer
.0B69 8E 0BC1         [4] 00284          stx    BufPtr
.                         00285
.0B6C                     00286 ReadLoop
.0B6C A2 C2           [2] 00287          ldx    #<ExecFCB  ; Read a character
.0B6E A9 0B           [2] 00288          lda    #>ExecFCB
.0B70 20 0260         [6] 00289          jsr    FMS
.0B73 D0 14 (0B89)  [2/3] 00290          bne    ChkErr
.                         00291
.0B75 C9 02           [2] 00292          cmp    #2        ; Quit if binary file
.0B77 F0 1E (0B97)  [2/3] 00293          beq    BadFile
.                         00294
.0B79 AE 0BC1         [4] 00295          ldx    BufPtr    ; Store the character
.0B7C 9D 0100         [5] 00296          sta    CmdBuf,X
.0B7F E8              [2] 00297          inx
.0B80 8E 0BC1         [4] 00298          stx    BufPtr
.                         00299
.0B83 C9 0D           [2] 00300          cmp    #$D       ; End of line?
.0B85 D0 E5 (0B6C)  [2/3] 00301          bne    ReadLoop  ; No, go read another
.                         00302
.0B87 18              [2] 00303          clc
.                         00304
.0B88 60              [6] 00305          rts
.                         00306
.0B89                     00307 ChkErr
.0B89 AD 0BC3         [4] 00308          lda    ExecFCB+FCBErr  ; Get error code
.0B8C C9 08           [2] 00309          cmp    #ErrEOF   ; Is it end of file?
.0B8E D0 05 (0B95)  [2/3] 00310          bne    GotError  ; No
.                         00311
.0B90 8D 0BC0         [4] 00312          sta    EOF       ; Indicate end of file
.                         00313
.0B93 18              [2] 00314          clc
.                         00315
.0B94 60              [6] 00316          rts
.                         00317
.0B95                     00318 GotError
.0B95 38              [2] 00319          sec
.                         00320
.0B96 60              [6] 00321          rts
.                         00322
.0B97                     00323 BadFile
.0B97 A2 AE           [2] 00324          ldx    #<Illegal
.0B99 A9 0B           [2] 00325          lda    #>Illegal
.                         00326
.0B9B 20 021E         [6] 00327          jsr    PSTRNG    ; Print String
.                         00328
.0B9E 4C 0B51         [3] 00329          jmp    Exit
.                         00330
.0BA1                     00331 Aborted
.0BA1 455845432041424F    00332          fcc    'EXEC ABORTED'
.0BA9 52544544
.0BAD 04                  00333          fcb    4
.                         00334
.0BAE                     00335 Illegal
.0BAE 494C4C4547414C20    00336          fcc    'ILLEGAL FILE TYPE'
.0BB6 46494C4520545950
.0BBE 45
.0BBF 04                  00337          fcb    4
.                         00338
.0BC0 00                  00339 EOF      fcb    0         ; Not zero if end of file
.                         00340
.0BC1                     00341 BufPtr   rmb    1         ; Index into command line buffer
.                         00342
.0BC2                     00343 ExecFCB

Top

cjs

Post subject: Re: A way to relocate code

Posted: Fri Sep 04, 2020 1:13 pm

Joined: Sat Dec 01, 2018 1:53 pm
Posts: 730
Location: Tokyo, Japan

The Apple II EDASM system offered relocation support; these were the type `R` files on Apple II DOS diskettes. It might be worth having a look at that to see how they did it. The manual includes an operation description (though just how to run the relocating loader, not actually how it works) and the relocatable file format.

_________________
Curt J. Sampson - github.com/0cjs

Top

BigEd

Post subject: Re: A way to relocate code

Posted: Fri Sep 04, 2020 1:38 pm

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10985
Location: England

The later revisions of Acorn's OS for the BBC Micro series also had a scheme for relocation: ROM code is normally assembled to run at 8000, but when run on the second processor can be loaded and run at B800 - if fixed up. I haven't looked at the code which does the fixing up.

Top

GARTHWILSON

Post subject: Re: A way to relocate code

Posted: Fri Sep 04, 2020 5:41 pm

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8543
Location: Southern California

BillG wrote:

GARTHWILSON wrote:

You can however reduce the overhead if you only allow movement in increments of 256 bytes. The overall memory penalty is less than you might think.

You are right, but not for that reason.

I was talking about truly relocatable code (per the link I gave), meaning it can be moved even after it's loaded and has been running. Other than my own post above, all the conversation here has been about being able to load it at different addresses, but not about the loaded code being able to get moved and keep running. This is the problem with modern PCs. We may have 16GB of RAM and still run out and have to start disc-swapping—not because we need anywhere near that much memory (let alone more), but because memory gradually gets fragmented so badly that the free memory is in a bazillion little pieces, none of them big enough to load the next thing you need. The HP-71, which I gave some description of in the "[OT] Thoughts on extending EhBasic?" topic, keeps moving things around in RAM. If one program deletes or re-sizes another file (yes, lots of files, and lots of programs, could be in RAM at the same time), even the program that's running might get scooted up or down in memory in the process of closing up the space so all the available RAM was together at one end, and it can keep running. Memory never gets fragmented.

_________________
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?

Top

BigEd

Post subject: Re: A way to relocate code

Posted: Fri Sep 04, 2020 5:55 pm

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10985
Location: England

(I think I'm right in saying that the kind of fragmentation you're describing afflicts large long-lived processes, such as browsers, mail clients, editors, development environments. I don't think it can affect the spawning of a new process, in a modern VM system. I believe the Mac's cooperative multitasking did allow for the run-time relocation and therefore compaction of memory allocations, which are a single shared resource for all applications. I believe (a bit less strongly) that the Amiga did not allow for run-time relocation of memory allocations. It did do load-time relocation of executables.)

Top

White Flame

Post subject: Re: A way to relocate code

Posted: Sat Sep 05, 2020 1:03 am

Joined: Tue Jul 24, 2012 2:27 am
Posts: 679

It's the MMU address translation which prevents OS-level memory fragmentation in modern stuff. Memory is allocated from arbitrary places in physical memory in fixed size chunks, and mapped into contiguous addresses in your process's local view of its address space. So your process never perceives the hardware piecemeal scattering or virtual memory shuffling, even at the machine code addressing level.

Of course the memory inside individual processes fragments, usually managed by C's malloc & free, dealing with a contiguous heap address space containing variable-length allocations.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

Top

GARTHWILSON

Post subject: Re: A way to relocate code

Posted: Sat Sep 05, 2020 1:34 am

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8543
Location: Southern California

White Flame, that makes a lot of sense, and explains the problem even better than what I was thinking. However in 6502 systems, we don't use an MMU, and it makes all the more sense then to be able to scoot things around in memory to keep from running out just because the available pieces of memory are not big enough even though collectively there would be plenty. The scooting (memory-moving) is not instant of course, and could be an annoyance if the kernel does it at the wrong times; but it could keep track of when the need is nigh and then carry it out at relatively idle times, or notify the user and give him the option to do it when he wants to. I never noticed any lags on my HP-71 when it does it. The disadvantage then is that programs have to be written for it (and accept a performance hit), or the kernel must recognize which ones are and which ones aren't, and leave the ones that aren't written for it alone.

_________________
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?

Top

Page 1 of 2

[ 25 posts ]

Go to page 1, 2 Next

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: Google [Bot] and 24 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum