Open fnuecke opened 8 years ago
No support for >20 bit for now tho, until someone can tell me an efficient way of mapping addresses without a lookup table
Use a linked list of ranges, and whichever one matches, remove it and readd it to the start of the list. I did something like this for OCMIPS, except the linked list was implemented as at least one int[] array pointing to TLB entries and was doubly-linked. It shouldn't be strictly necessary here though as you don't need to ensure that every entry is in the same index, although you could just have the ranges referenced in an ArrayList as well.
I would seriously consider having a few "pseudo" ranges available on-demand which are just open bus, mostly so a system doesn't get bogged down if you end up hitting an open bus range.
To make your life easier, you'll want to get the size rounded up to the nearest power of two and align it to that. Then you can just use something like (addr & ~(range.padSize-1))==range.addr
to do your comparison, and you can also open it up to potentially faster lookups.
With that said, you may want to consider having a flag which can be checked to see if you are actually on the open bus as some CPUs can be made to throw a bus error exception. This is optional, but may be useful. Or maybe just annoying. Either way, you can definitely probe for it.
A good value to use for open bus is -1 (all-ones).
Oh, and please make the address a long so I don't have to make you make it a long later on.
Hmm, so doing a linear search and reordering assuming the same range will be accessed again? That's a cool heuristic, I like it. Null-ranges as fillers make sense then, agreed. Instead of rounding, possibly making this a recursive data structure? I.e. create a number of "multi-ranges", each with their child linked list of ranges? Would allow grouping many "small" devices together and allow skipping them at once.
For "misses" I was thinking of triggering an interrupt, bad idea, good idea?
Regarding long, see other issue (in principle sure, just wanna do a quick performance test first).
doing a linear search and reordering assuming the same range will be accessed again
This is what I'm doing for TLB lookups on the MIPS3 core (and trust me when I say THIS DOES A LOT OF TLB LOOKUPS). I have not benchmarked this yet.
recursive data structures with multi-ranges
Yeah, that could work quite well. Something like this?
private class SubRange {
public long baseAddr; // aligned
public long subLength; // po2
public long fullLength; // does not need to be a po2
public int[] ids; // -ve == link to component[1-id]; +ve == link to subrange[id];
}
private ArrayList<SubRange> subrangeList;
private ArrayList<Component> componentList;
The interesting part of this is working out what heuristic to use when rebuilding the tree.
Also, make sure you cap the maximum possible physbits at N-2 (30 for int, 62 for long), solely so you can avoid really horrible pain. Like, really horrible pain.
triggering an interrupt on a miss
OK, that's a more elegant solution for detecting bus errors than I had in mind. In that case it would be important to have at least one "special" interrupt index for this very purpose.
I'd rather go with open bus. Either way is acceptable on MIPS, but on the Z80, using an interrupt (in this case NMI) will create more problems than it would solve, simply because even an NMI has to wait for your instruction to finish processing, and if you ever need to debug the issue, well, imagine if you ran a CALL opcode at the very last byte of the memory map... not to mention that you'd be disincentivised to use the NMI pin for general projects, considering how useful the NMI pin could be for redstone stuff.
I know I throw bus errors on OCMIPS but calculating memory size by scanning until you hit a bus error exception just complicates the interrupt handling routine. Having said that, such an approach should be unnecessary as we already can query this information from the bus controller. Besides, I can always enforce limits by passing the page fault handler to the main system handler when an address goes out of range, assuming I'm using identity paging of course.
A cleaner way of doing bus errors of course is to throw a Java exception, because if your CPU actually supports bus errors, you'll want to know about them then and there, rather than having to check a global. If it doesn't, though, you'll still have to fudge your own open bus value for the actual read, unless your NMI can actually stop an instruction and do the jump it needs to do.
So basically, opting for a fault rather than returning an open bus value doesn't really solve much, but adds complications that pretty much make it not worth it, and if your OS is Bug Free™ then you shouldn't even be entering into this situation anyway.
Added the index structure with the "clustered access" heuristic you suggested. Not nested yet, just a flat list, because I cba to do the balancing. Might read up on interval trees some more at a later point and see if one of those might be adaptable (from a quick glance the reordering would not really be compatible with the usual approach of balanced binary trees tho).
Since the interrupts are user-mappable, I suppose it could still be there in addition. So if someone wants to use it, they can, but nobody has to. If the CPU actually wants to do checks, some getter a la isMapped(long)
in the bus controller interface maybe? Throwing exceptions for misses seems... unnecessarily inefficient for all cases where the CPU doesn't care.
This will basically just change the maximum address value / address range. No support for >20 bit for now tho, until someone can tell me an efficient way of mapping addresses without a lookup table...
Also add a way to query this via the bus controller.