Как реализовать виртуальный кеш, tlb?

Question

[SergeySerge11]

Вроде прочел по теме много. Но хоть убей не могу понять, полностью проследить, как реализованы в kvm qemu virtualbox бош и другие. А именно тлб часть. Какой там алгоритм замещения(Или его там нету).
Как выглядит супер простой, но полный код. Структура, Схема, принцип. картинка.

// к примеру
struct TLB{
 TLBEntites[] entites; //  Какой размер в виртуальных машинах,  4098 или мегабайт
}
struct TLBEntites{
 int Tag;
 int ASID;
 void* RealAddress;
}
void* translate(int acid, int addr){
int offset=addr&0xfff; 
int tag=(addr>>(12+12));
int index=(addr>>12)&0xfff; //12 bit
// вот не могу понять, как это реализовано,
// все очень просто и понятно, если вот так, если  tlb хранит одну запись
  if(tlb[index].Tag==tag)
        return tlb[index].RealAddress | Offset;
////....
}
  // но в реальности там кеш линия, с RLU алгоритмом замещения.
// а значит  меня должно быть,  что-то типа этого
struct TLB{
    LruMap Line; //  // словарь + двусвязный список. 
}
struct LruMap{
 LinkedList<Node> nodes;
 Dictionary<int,TLBEntites> eniries; 
 Node head;
 Node tail;
}
    //  и тогда поиск будет где-то такой, где ф-ия Find  найдет нужную запись
   // путем log2N сравнений, и после если выполнит кучу инструкций, по политики замещения. 
if(tlb[index].Line.Find(tag), out void*addr)
  hit();  
// в итоге одна команда mov eax, ebx превращается, в 100 инструкций при попадание, поиск в
// словаре, выполнение действий по политике замещения(swap в head)
// Единственное что, после первого нахождения, можно перед поисков в линии сразу 
//сравнить с последним найденным, и скорей всего оно совпадет, и не надо политику обновлять.
// типа где-то так в реальности, но там нету вот этого Log2N сравнений, которые меня мучают,  
//так как все одновременно происходит в мультиплексоре

Я не понимаю, как можно при каждом получении адреса, а не знаю статистику, но наверное 50% ассемблерных инструкций это доступ к памяти.

Идеальное решение, сделать TLB размером 20бит для старшей части(без тега), массив с прямым отображением, адреса смещённого на 12 бит, по индексу. Где адрес индекс в массиве. Размер 1мб по 8-10 бит. Но тогда же по сути, при услужение, добавления ASID индикатора, то получается что этот индикатор то же самое что убранный тег. И я возвращаюсь сразу к началу(И тут либо опять LRU, или очищать буфер tlb).

Answer 1

[jcmvbkbc]

как реализованы в kvm qemu virtualbox бош и другие

В KVM -- никак, KVM использует фичу хостового процессора известную как 2-stage translation, при этом на первой стадии хостовый процессор выполняет трансляцию гостевого виртуального адреса в гостевой физический, аппаратно.

В QEMU -- я тебе уже писал как, с деталями и ссылочками в код. Но ты вместо того чтобы задавать конкретные вопросы опять начинаешь говорить что там всё сложно и непонятно.

Какой там алгоритм замещения(Или его там нету).

В QEMU собственный TLB QEMU прямого отображения, в случае промаха единственная запись TLB в которой может быть отображение для искомого виртуального адреса замещается новой трансляцией. Зависящий от эмулируемой архитектуры TLB эмулирует детали архитектуры, тебе нужно выбрать конкретную архитектуру чтобы её обсуждать, иначе мы закопаемся среди разных вариантов.

void* translate(int acid, int addr){

Похож на реализацию собственного TLB QEMU, только там нет ASID и в качестве тега используются все биты виртуального адреса кроме младших (обычно младших 12, но может быть меньше, если у эмулируемой архитектуры есть страницы меньшего размера).