View unanswered posts | View active topics It is currently Tue Mar 19, 2024 8:12 am



Reply to topic  [ 11 posts ] 
 Continuously Running Dynamic Program Locators 
Author Message

Joined: Sat Feb 02, 2013 9:40 am
Posts: 2095
Location: Canada
Yes, this topic suggests code is allowed to move around in memory at run time.

Suggested here is a means of loading programs into a fragmented memory system without virtual address translations. A program located in memory may be continuously reassigned to different address ranges in a dynamically located fashion at runtime as memory defragmentation / fragmentation occurs.
Most program loaders load programs into contiguous memory blocks. Enough contiguous memory must be free in order to load the program. Larger systems may rely on virtual memory addressing to make blocks of memory appear contiguous to the program.

However address translations for code are not overly valuable. In an FPGA implementation for example address translations may cost a clock cycle or two on every access. This is too expensive ! It’s better performance to use indirect function calls with a function call (or procedure call) table. Extra clock cycles occur only during the call operation then.
Most code could be relocated by a code relocation function in the operating system. Within subroutines relative branching makes relocating addresses for those targets unnecessary. Without virtual address translations, one task to be performed is to break programs up so that they can be loaded into a fragmented memory system. Doing so means that the call target addresses of subroutines within code would change depending on their physical location in a fragmented memory system. So a list of target call addresses (TAT target address table) must be maintained while the program is running.
The call target instruction may be used to contain the index in the TAT so that the address of the call target may be quickly updated in the TAT.

_________________
Robert Finch http://www.finitron.ca


Sat Apr 29, 2017 7:18 am
Profile WWW

Joined: Tue Dec 11, 2012 8:03 am
Posts: 285
Location: California
If programs can be moved after having been loaded, why not move one or more other entire programs if necessary to make one contiguous space for the new one getting loaded, so you don't have to break up a program and put it into a fragmented memory space. My Hewlett-Packard HP-71B handheld computer from the 1980's seems to be doing something like that. It's not multitasking, but it can have gobs of files in memory at the same time, including gobs of program files, and any program can call a subprogram in its own file or any other file (or even call itself recursively), up to 63 levels deep, storing environments. If a program deletes a file (of whatever type) that it no longer needs, and that file comes earlier in the file chain, the subsequent files get scooted down to close the gap that's left, so that all available memory is left at the end of that memory port. The program keeps going (although hopefully you didn't delete a program you have to get back to later!). It's all transparent to the user, and I've never noticed any delays (although we're not talking about multimegabyte files; they're seldom more than five or ten K. (I have 177KB of RAM and a similar amount of ROM in mine, limited by my budget and the high cost of fleapower SRAM at the time. I have thousands of pages of documentation on it, and I have not delved into it to learn the innards. I will be interested in the discussion here though, to learn whatever I can.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources


Sat Apr 29, 2017 9:34 am
Profile WWW

Joined: Sat Feb 02, 2013 9:40 am
Posts: 2095
Location: Canada
I had a radio shack handheld computer I got on sale in the 80's. Ran BASIC but it had only 1.5k ram. One day in class I sat on it and busted the screen. I used it to store formulas for school. I took it apart and found out it had 3 2114's static ram chips. It was all CMOS. Probably a four bit or 12 bit cpu.
The HP handheld sounds quite powerful for the time. It sounds like it uses some sort of heap managed relocations that could be similar to what I'm thinking. Hand-held computers these days are cell telephones.

Loading into a fragmented memory system allows programs to be shape-shifting. This means that the size and shape of the program and subroutines can change at runtime. It might make for some interesting displays of memory usage. Another thought here is to make memory two or three dimensional and give the program directions for movement in memory.
I think each subroutine could be loaded into heap allocated space.
I envision a program composed of a table of addresses. All a relocator has to do is take the subroutine address and stuff it into the table at the correct index. A relocation could be done whenever the subroutine moves in memory.

What I'm after is instructions in the instruction set that are simple and would support this type of thing. It looks to me like it could be supported without any special instructions, but a memory indirect call might help.

_________________
Robert Finch http://www.finitron.ca


Mon May 01, 2017 4:31 pm
Profile WWW

Joined: Tue Dec 11, 2012 8:03 am
Posts: 285
Location: California
robfinch wrote:
What I'm after is instructions in the instruction set that are simple and would support this type of thing. It looks to me like it could be supported without any special instructions, but a memory indirect call might help.

That sounds like what I had in mind for the 32-bit offset registers that would take the place of the 65816's data-bank, program-bank, and direct-page registers in the 65Org32. Every program can think it starts at address 0 regardless of where it got loaded and regardless of getting moved after it's already in use. If it refers to another program in memory which might not move in unison with it, then there would have to be some sort of table that would get adjusted; but otherwise it works with no MMU or indirects other than the offset which is an addition that happens automatically in the processor itself in most cycles.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources


Mon May 01, 2017 10:17 pm
Profile WWW

Joined: Sat Feb 02, 2013 9:40 am
Posts: 2095
Location: Canada
I'm getting fed up with the complexity of the FT832 and am thinking of changing it radically (or starting a new project FT833). 32 bit offset register you mentioned are looking pretty good right now. One problem is how to set the register. As soon as it's set the program location would change so unless there was code at the right address it would crash. This problem is solved by the 8086 with far jump instruction that sets both the code segment and instruction pointer at the same time. Something similar could be done but it'd be a pretty long instruction with a 24 bit PC, 32 bit offset setting and 16 bit opcode. That 72 bits ! The problem is it opens a whole can of worms of jumps, calls, and returns that specify the offset.
Presumably there would be more than one program present in the system which is why the need for an offset register. So switching the offset might only be needed when switching programs. I'm wondering if there's a way to have a ROM mapped in an aliased fashion throughout the memory space so that it always shows up somewhere in the program space. The offset could be made shorter by it having only page (256 byte) granularity. It one less byte to pass around then.

_________________
Robert Finch http://www.finitron.ca


Tue Jun 06, 2017 4:10 am
Profile WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1780
The PDP-8 has a feature whereby a bank change doesn't take effect until the next branch - or something like that. Could be worth considering. It's an extra bit of state in the machine, which would need to be saved if there's an interrupt.


Tue Jun 06, 2017 5:47 am
Profile

Joined: Tue Dec 11, 2012 8:03 am
Posts: 285
Location: California
The PIC16 does that too. It got around certain limitations; but banking and paging on that thing are very inefficient. I've posted this example on the 6502.org forum, of a single-byte table look-up, where table might be anywhere in ROM. The inefficiency comes from more than just the program counter latch high byte (called PCLATH), but it might prompt considerations that don't initially come to mind:

Code:
6502: 4-5 clocks        LDA address,X

Code:
PIC:  48 clocks, to do what the 6502 does in 4 or 5 clocks!  (This code is
from slide 234 of the seminar, and the same as what's in AN556 Example 5.)

       ORG    0x10          ; Page 0
       MOVLW  LOW (Table)   ; Low byte of address     4
       ADDWF  offset,F      ; added to offset.        4
       MOVLW  HIGH (Table)  ; High 5 bits of address  4
       BTFSC  STATUS, C     ;   Page crossed?         4
       ADDLW  1             ; Yes...Inc high address  4
       MOVWF  PCLATH        ; Load high address       4
       MOVF   offset,W                                4
       CALL   Table                                   8

       ORG    H'800'        ; page 1
Table:
       ADDWF  PCL,F         ; Calc table offset       4
       RETLW  'A'                                     8
       RETLW  'B'
       RETLW  'C'
       RETLW  'D'
       etc.

Another PIC stinker: If an interrupt hits immediately before the PCL-modifying instruction above, it will misbehave after the return from interrupt, and you'll get the RETLW 'A' even if you wanted a different one; so you have to disable interrupts for the table look-up further lengthening the code and slowing things down and causing a longer interrupt latency. This is from AN556, bottom of page 3.

The PIC has to use different code if the table is in RAM. It can't use the same code for ROM and RAM like the 6502 can. Furthermore, if you index past the end of the table in ROM, you won't just get bad data-- you'll crash.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources


Tue Jun 06, 2017 6:36 am
Profile WWW

Joined: Sat Feb 02, 2013 9:40 am
Posts: 2095
Location: Canada
Quote:
The PDP-8 has a feature whereby a bank change doesn't take effect until the next branch - or something like that. Could be worth considering. It's an extra bit of state in the machine, which would need to be saved if there's an interrupt.
Seems like a reasonable way of performing the bank switch. It gets tricky if one wants to call code in another program offset. The current offset would have to be pushed onto the stack with PHx instructions before JSR'ing, then loaded back into a latch with PLx instructions for RTS. So maybe PHO, PLO instructions to push / pull the offset latch would help. Next the RTL / RTS instructions would have to be able to trigger a switch. Next is what to do on an IRQ ? My though it is to have the program offset stored in a small internal stack.
Quote:
It's an extra bit of state in the machine, which would need to be saved if there's an interrupt
It seems almost any extra capabilities added to the 6502 would require extra state bits. It might be best to simply expand the status register to 16 bits. Multi-level interrupt masks could be added then too. It's one extra byte to save on interrupt.
Quote:
but banking and paging on that thing are very inefficient.
Sounds like the PIC is somewhat inefficient here. It reminds me of the code for some VGA controllers. Some controllers were a lot more inefficient at doing things like switching modes or plotting points than others.

_________________
Robert Finch http://www.finitron.ca


Tue Jun 06, 2017 11:09 am
Profile WWW

Joined: Sat Feb 02, 2013 9:40 am
Posts: 2095
Location: Canada
Well I spent most of the day working on the '833 with a program offset register only to find out it might be too simple. The problem is that when the program offset is changed, the stack is lost because all addresses are calculated as a sum with the program offset. The target routine needs to save the stack pointer somewhere then set the stack pointer to a place it knows is safe. The question is how do you change the stack pointer without using any registers ? It looks like a dozen lines of code of pre/post amble for every function to be called. On the return the old stack pointer has to be restored. It might help to have two offset registers, one for code and one for data. But it starts to look like the x86. How to deal with parameters passed on the stack ?

Code:
; To call routine using another offset
LDO   #TargetOffset
JSR   Target

Code:
; Preamble to subroutine, switches the stack
SEI
STX reg_x_save
TSX
STX reg_sp_save
LDX #safe_sp
TXS
LDX reg_x_save
CLI
....

_________________
Robert Finch http://www.finitron.ca


Wed Jun 07, 2017 1:00 am
Profile WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1780
If you have a bunch of architectural state, and you're having trouble updating, is there a case for making a shadow set, and making your update commands change the shadow, with a final atomic swap?


Wed Jun 07, 2017 6:55 am
Profile

Joined: Sat Feb 02, 2013 9:40 am
Posts: 2095
Location: Canada
Yes, there is a case. But that means adding additional registers and instructions. I'd hoped for something simpler, but I guess that can't be had without jumping through a lot of software hoops. I found a way to deal with parameters but is it ever inefficient. It involves storing the stack pointer to zero page memory then using indirect addressing to access the parameters. Of course the old offset register value also has to be added to the stack pointer.
The FT832 does atomic swaps between register sets with the JCR / RTC instructions. Well actually they place the entire register set on an internal stack, then load from a template register set atomically (in the same instruction). So everything at the target is setup properly (stack, data bank, direct page, etc). Takes about 12 clock cycles, but that's fast compared to doing things with software.

_________________
Robert Finch http://www.finitron.ca


Fri Jun 09, 2017 12:07 am
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 11 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


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

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software