Friday, August 31, 2012

Emulation of Hardware. CPU & Memory

There are tens of hardware platforms (although, some people would say that there is only one - computer ;-) ). Each one has its own advantages over others and disadvantages as well. For example Intel is the most used platform for desktops, ARM and MIPS are widely used in embedded systems and so on. Sometimes, a need may arise to test/debug executable code written for platform other then the one you have access to. For example, what if you have to run ARM code while using Intel based desktop? In most cases, this is not a problem at all due to a large amount of available platform emulators (e.g. QEMU and many others). However, even though QEMU is quite a powerful tool, there are certain cases when it is not helpful (at least not without certain modifications).

Note for nerds:
Yes, there are such cases - if you have not seen one, does not mean they do not exist. 
The code in this article is for demonstration purposes only - checks for errors may be omitted. It may be unoptimized.
Yes, there may be better ways.

Either forced by current needs or just for fun, you may want to write your own emulator for any existing (or not existing) platform. You may check this article to see how a simplistic CPU may be designed and implemented. However, CPU is only a tiny (although, important) part of your emulator. There are many other things that you would have to take care of, such as memory, IO devices, etc. Of course, the complexity of the implementation depends on how isolated you want your emulator to be. 

As you may understand from the title of this article, we are going to concentrate on the CPU to Memory (RAM) interface. It may be a good idea to define how much memory should your emulator support (define the width of the address line) in advance. For example, if you are going to support at most 64 kB, then 16 bit addressing mode would be enough. In such case, you may simply allocate a continuous memory area and access it directly. However, what if you plan to support 1 or 2 or even more gigabytes? Although, it would not necessarily be used at once, but your architecture may imply this. You definitely would not want to make such a huge allocation. Especially not if the software you are planning to run uses a tiny bit of memory in lower address space, a tiny bit in the upper and itself is loaded somewhere in the middle. If this is the situation, then you should implement a kind of a paging mechanism, which would only allocate pages for addresses which are actually being used.


Paging

Let's make some definitions to deal with pages:

#define PAGE_SIZE 0x1000 // You may choose to use other size
#define PAFE_MASK 0x0FFF // This depends on the value of PAGE_SIZE

typedef struct _page_t
{
   struct _page_t*   previous, next;
   unsigned long     base;  // Address in the emulated memory represented by this page
   unsigned int      flags; //Whatever flags you want your pages to have
   unsigned char*    mem;   // Pointer to the actual allocated memory
}page_t;

The mechanism is quite similar to the actual paging mechanism used today, except that you do not have to use page tables as most of the time a simple linked list of pages is enough and that you are not mapping virtual memory to physical, but mapping emulated memory to the virtual memory which is accessible for the emulator.

previous and next - pointers to other page_t structures in the linked list of pages;
base - lower address of the emulated memory represented by this page;
flags - any attributes you would like your pages to have (e.g. is it writable or executable, etc.);
mem - pointer to the memory area actually allocated by the emulator.

Using such mechanism will reduce the overall memory usage as you would have to allocate only those memory areas used by the software you are running on your emulator.


Page Management

It is, of course, up to you how to manage this kind of paging, but, as it seems to me, it may be a good idea to implement a set of functions to manage the sorted (by base) linked list of pages:

page_t* memory_page_alloc(void);

This function would simply return a pointer to an allocated page_t structure. Don't forget to allocate real memory area of PAGE_SIZE and store a pointed to it in page_t->mem

void  memory_page_release(page_t** pg);

This function releases all the resources allocated for a page. This includes the memory which actually represents the page and is pointed to by page_t->mem and the page_t structure itself.

int  memory_page_add(page_t** page_list, unsigned long base);

This function is responsible for allocation of a new page, which would represent memory starting at base and its insertion into the sorted linked list of pages.
*page_list - pointer to the first page in the linked list of pages;
base - beginning address of the emulated memory of size PAGE_SIZE.
Its return value should tell you whether a page has been added or an error occurred during memory allocations.


Memory Access Emulation

Due to the fact that we are not talking about one consistent array, but rather several separated memory areas (from the emulator's point of view) it makes sense to write a couple of functions that would perform read/write operations from/to the emulated memory.

int memory_read_byte(page_t* pg_list, unsigned long address, unsigned char* byte);

This function is responsible for reading a single byte from the emulated memory pointed by address. The read byte is returned into location pointed by byte. It walks the linked list of pages looking for a page where page_t->base <= address && (page_t->base + PAGE_SIZE) > address. If there is no such page, then it either allocates and adds it to the list of pages, then performs the read operation or simply returns error (this may be helpful in order to emulate memory access violations). It is up to you to define the behavior of this function in such situation. In fact, you may define an internal flag to enable/disable automatic page allocations.

int memory_write_byte(page_t* pg_list, unsigned long address, unsigned char byte);

This function is almost identical to the one above, except that it writes a single byte to the emulated memory. Its behavior should be the same as memory_read_byte.


It is definitely not that good to only be able to transfer one byte at a time, so you are more then welcome to implement functions for larger transfers. However, you will need to be careful in those cases when such transfer involves two pages and check that both pages are allocated (meaning accessible).


Of course, there are many more things to emulate like IO devices, possibly network adapters, but memory is the most important. But this goes far beyond the scope of this article.

Hope this article was informative. See you at the next.